FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

c/c++

xv6: mkfsの実装を読む

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

Cygwinでxv6を実行する

下準備編 既に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>…

迷路の最短経路

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

C言語で2次元配列を動的に割り当てる4つの方法

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

Unix time = 1234567890

#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>…

struct

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

bmp2ascii

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

プログラマは0から数える話

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

オレオレ3D on xlib

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

情オリ本選 問1-4

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

困難版ハノイの塔を解いてみた

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

JOI予選で使ったやつ

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

パソコン甲子園2007予選問題 問08

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

Brainfuck in C-Language

これで、プログラミング言語のインタプリタを実装したことがあるって胸を張って言える……かも。 #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>…

nagator Ver 0.02

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

もっと低レベルなことがしたいんです

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

int main = 195 に衝撃を受けた17の冬

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 予選問題 問2

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

もっとアルゴリズみ!

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

epoch@まつやま 予選の問3 オレ的解答

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年度予選問題まとめ

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

おれおれリバーシ Ver 1.00

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

ジグソーパズルくらいでパソコン使うなよ、夏

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

パソコン甲子園の問題ってムズくね。

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