mkfsの実装をだいたい理解したので，xv6のファイルシステムの仕組みを中心に覚え書きとして残しておく。 ファイルシステムのブロック構造 ファイルシステムは複数のブロックで構成される。1ブロックは512バイト。 最初の1ブロックはブート用なのでfs.imgでは…

下準備編 既にCygwinを使っていた人も専用の環境として新規にCygwinをインストールした方がいいかもね。 結構バージョンの組み合わせによっても動く動かないがあるみたい。 Cygwinをインストールする 下記のパッケージを選択してインストール： Devel/binuti…

#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 void quick_sort(int *array, int left, int right) { int x = left; int y = right; int pivot = array[(left+right)/2]; if (left >= right) { return; } while (x <= y) { while (x <= right && array[x] < p</time.h></stdlib.h></stdio.h>…

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。ダイクストラとか大昔に書いた記憶があるけど完全に忘却の彼方だったので，適当にCで書いたらこうなった。スタート地点から深さ優先で探索してコストを求めていく感じで。普通はキューで探索す…

２次元配列を動的割り当てしたいそんなとき，C言語ならキモくなるかも。検索エンジンから来る人がそれなりに居るようなので，解説画像を追加しました（2014/12/05）。 各行のデータを保持する配列と各行へのポインタを保持する配列に分けて確保 おそらく最も…

#include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) { time_t t, t_last; t_last = 1234567890; while ('A') { t = time(NULL); if (t >= t_last) break; printf("now=%d, remaining=%d\n", t, t_last - t); sleep(1); } printf("チョコくれよヽ(`Д´)ﾉｳﾜｧｧﾝ\n");</time.h></stdlib.h></stdio.h>…

http://urasoku.blog106.fc2.com/blog-entry-600.html C言語 #include <stdio.h> #include <string.h> #include <stdlib.h> void tr(char *src, char *cmp, char *str) { char *tmp, *index; int p_tmp, p_src; int len_before, len_after; index = strstr(src, cmp); if (!index) return;</stdlib.h></string.h></stdio.h>…

いつも typedef struct { int id; char *name; } data_t; data_t data[100]; みたいに書いてるもんだから struct data_t { int id; char *name; }; struct data_t data[100]; みたいに書いてあると一瞬意味が分からなくて混乱するどこまでが型名でどこからが…

ニコニコとかでこの手のプログラムをよく見かけるので，いちからC言語で書いてみた。################################################ ################################################ ################################################ #############…

歴史的な理由 もともとC言語の array[i] は *(array + i) の構文糖であるが、もし配列のインデックスが1から始まるとすると array[i] を *(array + i - 1) としなければならなくなって都合が悪い。よって、C言語では配列のインデックスを0から始まるものとし…

自前で簡単な3Dっぽいものを書いてみた。ワイヤーフレームでできた立方体が一定方向に回転するだけのプログラム。OpenGLやSDLなどのライブラリは未使用だが、適当に回転させているため、次第に誤差が蓄積されて謎の立体になってしまう。これを発展させて、今…

コードを書いて理解しなければ、セミナーに行った意味がない！ joi2008.zip という訳で、情報オリンピック本選・問1-4の暫定回答（にわかC++版）を恐れを知らずにうｐしてみる。会場にUSBメモリを持って行くのを忘れたから、ソースは帰ってからぐだぐだと書…

「困難版ハノイの塔」とは、深夜の『コマ大なんとか』とかいう番組で取り上げられていた変形版ハノイの塔のこと。昨日の授業でこの問題の話が出てきたので、いっちょプログラムを作ってみた。 あうとらいん この問題は有名な「ハノイの塔」というパズルをベ…

実行して問題番号を入力すると、ソースをコンパイルして出力ファイルを生成するプログラム。ただし、問題のソースを 1.cpp, 2.cpp, ... というファイル名にしておく必要がある。別にシェルスクリプトでもいいじゃんという脳内意見もあったが、シェルスクリプ…

パソコン甲子園2007予選問題 本番で「スパイダー人」というシュールな単語に戦意を喪失させられたアレ。当然時間内では解けなかったっていうか、そもそもそっちまで時間が回らなかった。単純な制約付き最短経路問題→ダイクストラのアルゴリズムで解ける！と…

これで、プログラミング言語のインタプリタを実装したことがあるって胸を張って言える……かも。 #include <stdio.h> int main(int argc, char *argv[]) { char array[1024] = { 0 }; int stack[32], ptr = 0, stk = 0; int nest, c; FILE *fp; if (argc < 2) { fprintf</stdio.h>…

長門とのチャットをシミュレートするこそばゆいプログラムを作ったよ！ さりげなくバージョンアップしたので再掲。なぎささんとこのスクリプトに触発されたっていうのが動機。機能的にもビジュアル的にも元の方が上なので、ウチのは明らかに劣化移植版。しか…

つー訳で、幾度となくobjdumpしてメモリアドレスと命令を見比べながら、試行錯誤でmainが配列なコードを書いてみた。数時間ぐらい余裕で経過。オレは一体何をしているんだ。 $ cat hoge.c #include <stdio.h> unsigned int main[] = { 0xc7e58955, 0x00682404, 0x11e8</stdio.h>…

mainとは何なのか(1) - バリケンのRuby日記 - Rubyist int main = 195; // Σ (ﾟДﾟ;） 195 = 0xc3 であることを踏まえ、コンパイルしたバイナリをobjdumpとかいうコマンドで覗いてみる。 $ objdump -D 195.exe 00402000 <_main>: 402000: c3 retうわー。計算機という</_main>…

都市数が20以下ぐらいであれば、動的計画法を使ってTSPの厳密解を求めることが可能。その概要は以下の通り。state を「到達した都市の状態を表すビット列」、cost[state][i] を「都市 i を訪れて状態 state になったときの最小コスト」とすると、 cost を十…

SuperCon 2007 予選問題（PDF） 「Algorithms with Python / 欲張り法, 動的計画法」を参考にしつつ、動的計画法で普通に実装してみた。「普通に」実装するまでにどんだけ時間かかってるんだ、っていう。確認した限りでは正しい答えを導いてくれるはず。計算…

ダイクストラ法（最短経路問題） 上のページの解説を参考に、擬似コードをC言語に翻訳してみた。こういうアルゴリズムの理解がすらすらとできるくらいには、オレは少しは成長したのかなあ。 #include <stdio.h> typedef struct { int edges_to[10]; int edges_cost[10</stdio.h>…

EPOCH＠まつやま予選問題 問3 - カビの生えた雑記に便乗して。もう提出を締め切った後だから問題ないよね。あっちの回答よりも行数が多いのは何故だろう！ #include <stdio.h> /* サイコロの状態を表す構造体 */ struct { int top, right, near; } state = { 2, 1, 3 </stdio.h>…

しばらく前から少しずつ作ってた数独を解くプログラムがやっと完成したよー。ムズい問題も解けるよー。色んな問題をやらせてみたけどどうやらちゃんと動作するようだよー。ソースは300行程度だよー。アルゴリズムは2種類の確定サーチとバックトラックを組み…

ソースを見直したらなんか無駄な処理しまくってるっぽかったので書き直した。この暇人め。バックトラックも実装したかったんだけど、step2まで実装したところで力尽きたので今日はここまで。実は機能もソースの行数もあまり変わっていない罠。解法アルゴリズ…

パソコン甲子園2005年度予選問題の問11より。西暦で入力された年月日を和暦表示に変換せよという問題。西暦と和暦の対応表は以下の通り。 元号 期間 明治 1868-09-08 〜 1912-07-29 大正 1912-07-30 〜 1926-12-24 昭和 1926-12-25 〜 1989-01-07 平成 1989-…

ここしばらく取り組んでた、パソコン甲子園2006年度予選問題について、自分なりの解答を公開してみた。 パソコン甲子園 (リンク先はてな外) 稚拙なコードなんであんまり参考にはならないと思われ。もし間違い、バグ等あったらここのコメント欄かtondolまでメ…

オセロともいう。とっても標準的で普通なリバーシのプログラムを作ってみた。言語はC言語、ソースは400行に満たないぐらい。コンピュータのアルゴリズムは無能なランダムなので、とっても弱いはず。だけどオレは負けました。素晴らしい。駒を置く位置は、2桁…

という訳で、パソコン甲子園2006年度予選の例題10を解くプログラムが遂に完成しますた。ジグソーパズルの枠とピースの組み合わせが複数与えられ、それぞれのピースの組み合わせについて、パズルを完成させることができるかどうかを判定するというもの。これ…

ティーチャーは「基本的な問題」とおっしゃるが、これが基本的な問題ならばオレはやはりまだまだ初心者ということである。問題の中にはJavaやVB.NETなどの基本ライブラリが充実した言語の方が明らかにプログラミングしやすいものもあり、C言語しか使えない俺…