$BB.;;%F%/(B
Kazuo Fox DOHZONO
Hideki Kato <ka...@pop12.odn.ne.jp> writes:
> 一般化した
> ｎ進法でｎ倍するのは一桁左にずらす
> １／ｎ倍するのは一桁右にずらす
> ならばここでいいような．
> ＃普段使ってますよね？
# 再び fj.comp ネタっぽいので Newsgroups: もそんな感じで.
IOCCC (International Obfuscated C Code Contest) の 1992 年の "Most
Useful Algorithm" 賞に輝いた albert.c がちょっと「おおっ」と思わせる
作品でした.
| $ time albert 1234567890123456789
| 3
| 3
| 101
| 3541
| 3607
| 3803
| At most one remains
|
| real 0m0.031s
| user 0m0.015s
| sys 0m0.014s
つまり「1234567890123456789 の因数は ３, 3, 101, 3541, 3607, 3803 と後
一つです」と言っているわけですね (「後一つ」は 27961).
この巨大数の因数分解に多倍長演算ライブラリの類は一切使われていません
(確かそういうのはコンテストの要項から外れたはず). 当然剰余命令も一切あ
りません. そこそこ早くて, しかも (そういうコンテストですから) ソースも
わざと見にくくしているにも関わらず, 150 行程度しかありません.
なんて凄いプログラムなんだ! 凄いでしょ? 凄いでしょ?
というわけで, 以下ネタバレ :-)
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
# なんか今見たらデバッグ版と称して見易いバージョンが同梱されてる…. 当
# 時必死になって解読したのになぁ.
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
以下の説明では一桁の因数 (2, 3, 5, 7) は見つけられないはずですが, 上の
例で何故 3 が出力されているのかの説明は勘弁してください (もうあの頃の
情熱はないので). 実際見易いバージョンでは (数値の取り込み方法の制限から)
3 は出てきませんが, アルゴリズム自体は一桁の基数にも対応出来るはずです.
実際のプログラムとはちょっと違いますが, 要はこんな感じ.
まずは与えられた文字列を一桁毎に配列に入れていく. この時に文字の
'0'～'9' を数の 0～9 に変換するので, 配列の各要素は十進表現の一桁に
なる.
「基数」を 10 とする.
…で始まるわけですが, 折角疑似コードなので一桁にも対応させましょう.
与えられた数の二進表現の各桁を一要素として配列にする. つまり, 配列の
一要素＝一桁＝一ビット.
「基数」を 2 とする.
while (桁が二桁以上ある限り) {
while (最下位桁が 0 である間) {
「基数」を因数として表示.
最下位桁を破棄し, その上の桁を新たな最下位桁とする.
}
配列全体は「基数」進法なので, これを「基数+1」進法に変換する. [*]
「基数」に 1 加える.
}
“後一つあるよ”と表示して終り.
こんだけです :-)
キモは [*] の部分で, 通常の基数変換と異なり基数が 1 だけ違うことを利用
したアルゴリズムになっています (とはいっても効率は…).
; 「基数」表現から「基数+1」表現への変換
for (i;; 最上位桁の次から最下位桁に向けて) {
for (j;; i 桁から最上位桁に向けて) {
j 桁の数から一つ上の桁の数を減じる;
if (j 桁の数が負なら) {
j 桁に「基数+1」を加える;
j 桁の一つ上の桁の数から 1 減じる;
}
}
}
以上, 表現は上の説明に準じています.
つまり, この方法では配列の一要素の最大値を上限とした因数への分解が可能
なわけです. 確かこの辺りの絡みで最後の要素の内容を表示してないんじゃな
かったかなー.
あんまり useful でもないと思ったのは私だけでしょうか :-p
KATAYAMA Yoshio
doh...@hf.rim.or.jp (Kazuo Fox DOHZONO) writes:
> In article <403ac18d.6925%ka...@pop12.odn.ne.jp>
> Hideki Kato <ka...@pop12.odn.ne.jp> writes:
>
> > 一般化した
> > ｎ進法でｎ倍するのは一桁左にずらす
> > １／ｎ倍するのは一桁右にずらす
> > ならばここでいいような．
> > ＃普段使ってますよね？
> # 再び fj.comp ネタっぽいので Newsgroups: もそんな感じで.
小数点以下を切捨てる除算で、負数の場合も考える時は、切捨てる方向
によってはＮＧです。Ｃで、i が int 型の時、i/4 と i>>2 は、多く
の処理系で異なる結果になります。
元の話題に戻って、、、
(1) 2桁の掛け算で、一の桁が5で、十の桁が 1違いの場合、
(10*a + 5) * (10*(a+1) + 5) = 100*a(a+2) + 75
＃↑は、たまに使います
(2) n 進法で n-1 で割った剰余は、各桁の数字を足して n-1 で割った
剰余に等しい → 1桁になるまで各桁の数字を足す
--
片山＠ＰＦＵ
Takao Ono
<qkp4qtd...@dash.tokyo.pfu.co.jp>の記事において
ka...@pfu.fujitsu.comさんは書きました。
kate> 小数点以下を切捨てる除算で、負数の場合も考える時は、切捨てる方向
kate> によってはＮＧです。Ｃで、i が int 型の時、i/4 と i>>2 は、多く
kate> の処理系で異なる結果になります。
i / 4 が truncation toward zero であるのに対し, i >> 2 は負であっ
てもたいていの場合 truncation toward -infinity ですからね.
# i >> 2 が正 (つまり logical shift) でも文句はいえない.
--
名古屋大学大学院 情報科学研究科 計算機数理科学専攻
小野 孝男
KATAYAMA Yoshio
> kate> 小数点以下を切捨てる除算で、負数の場合も考える時は、切捨てる方向
> kate> によってはＮＧです。Ｃで、i が int 型の時、i/4 と i>>2 は、多く
> kate> の処理系で異なる結果になります。
> i / 4 が truncation toward zero であるのに対し, i >> 2 は負であっ
> てもたいていの場合 truncation toward -infinity ですからね.
C99 で truncation toward zero が規定されたんですね。見落としてま
した。
> # i >> 2 が正 (つまり logical shift) でも文句はいえない.
という実装をした処理系に実際に出会った気がするのですが、どの処理
系だったか思い出せません。
＃老化現象が進んでる、、、
--
片山＠ＰＦＵ