C/C++の良問題鑑賞スレ

良問を広く晒して世の中を良くしよう！
解きたい人は解いてもいいよ

★関連スレ
C/C++の宿題片付けます 163代目
http://toro.2ch.net/...cgi/tech/1361082416/

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

なんだアイちゃんが立てたのか

【報告者へ】
報告の際は以下を行うことを推奨します。
・質問は【報告テンプレ】を利用してください。 >>2以降にあります。
・問題文は、出題されたまま全文を書いてください。
・問題文やコードをリンクするときは、一言内容にについて説明をつけましょう。
・計算問題は数式をあげ、どのような計算をするのか詳しく説明してください。
・エラーは、その詳細と発生した行を書きましょう。エラーメッセージはコピペしてください。
・後から問題に付け足しするのはコラー！！です。付け足しは作業を無駄にしがちです。
・なりすましを防ぎたいのならトリップを使ってください。名前欄に、「#」に続けて任意の文字列を入力して投稿すると、その文字列を知らない他人に騙られることを防ぐことができます。

【報告テンプレ】
[1] 授業単元名：
[2] 問題文(含コード&リンク)：
[3] 環境
　[3.1] OS： (Windows/Linux/等々)
　[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)
　[3.3] 言語： (C/C++/どちらでも可 のいずれか)
（以下、どうしても回答がほしい人は追加して記入してください。）
[4] 期限： ([yyyy年mm月dd日hh:mmまで] または [無期限] のいずれか)
[5] その他の制限： (どこまで習っているか、標準ライブラリは使ってはいけない等々)
【アップローダー】(質問が長い時はココ使うと便利　回答者もコードが長ければここに)
http://codepad.org/、http://ideone.com/、http://pastebin.com/
【C 関数検索 man on WWW】 http://www.linux.or.jp/JM/index.html
【過去ログ検索】　　　　　　　　http://chomework.sakura.ne.jp/
【wiki】　　　　　　　　　　　　　　 http://www23.atwiki.jp/homework/

優れた問いは、時に優れた答えに勝る
>>1乙

おれが出題してやるよ

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京極大学霊長類研究所

アイちゃんにしてはよくやったよな

手の込んだ教えて君だよな

[1] 授業単元名：暇潰し
[2] 問題文：できる限り速くフーリエ変換を行う関数を作れ。
[3] 環境
　[3.1] OS：Windows 7
　[3.2] コンパイラ：VC++2010
　[3.3] 言語：C/C++どちらでも可

[1] 授業単元名：FizzBuzzクイズ
[2] 問題文(含コード&リンク)：
[3] 環境
　[3.1] OS： (Windows/Linux/等々)特に問わない
　[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)特に問わない
　[3.3] 言語： (C/C++/どちらでも可 のいずれか)C++/Java

http://kohada.2ch.ne.../prog/1209467166/401
FizzBuzzクイズ

1.fizz.buzz #=> 1
3.fizz.buzz #=> "Fizz"
5.fizz.buzz #=> "Buzz"
15.fizz.buzz #=> "FizzBuzz"
999.fizz.buzz #=> 999

となるようなメソッドfizz、buzzは定義可能か？
可能である場合、同様にgizzを追加定義し、
7.fizz.buzz.gizz #=> "Gizz"
21.fizz.buzz.gizz #=> "FizzGizz"
35.fizz.buzz.gizz #=> "BuzzGizz"
105.fizz.buzz.gizz #=> "FizzBuzzGizz"
105.fizz.gizz.buzz #=> "FizzGizzBuzz" と拡張・応用ができるか？

メソッドのコールに()が必須の言語では 3.fizz().buzz() 形式でも構わない。
オープンクラス機構やメソッドのない言語では関数（buzz(fizz(3)) #=> "Fizz" など）で。

QZついにやけくそ

QZにはもっと活動してもらって、敵対視する人間のストレスを蓄積させていって欲しい

などというわざとらしい自作自演発狂カキコ

荒らされないなら、宿題依頼はこちらですればいいかも

っと再び犯罪行為を推奨

>>11
判定：C
理由：
フーリエ変換を高速に行う手法を紹介したものは類書多数（例えばhttp://www.amazon.co.jp/dp/4789830322）
出題者の工夫やセンスが皆無

[1] 授業単元名：暇潰し
[2] 問題文：形式言語で書かれた平面幾何学の問題を解く人工知能(ソルバー)を作れ。
[3] 環境
　[3.1] OS：Windows 7
　[3.2] コンパイラ：VC++2012
　[3.3] 言語：C++

[1] 授業単元名：暇潰し
[2] 問題文：C++で浮動小数点数(double型)の四則演算と同時に誤差の範囲を計算するクラスを作れ。
[3] 環境
　[3.1] OS：Linux
　[3.2] コンパイラ：clang
　[3.3] 言語：C++

[1] 授業単元名：暇潰し
[2] 問題文：レインボーテーブルを使って２ちゃんねるトリップをクラックするプログラムを作れ。
[3] 環境
　[3.1] OS：Linux
　[3.2] コンパイラ：g++
　[3.3] 言語：C++

[1] 授業単元名：暇潰し
[2] 問題文：円周率を高速に計算するプログラムを作れ。ただし、充分大きいN桁の計算が終わる度に計算内容をファイルに保存して途中から計算を再開できるようにせよ。
[3] 環境
　[3.1] OS：Linux
　[3.2] コンパイラ：clang
　[3.3] 言語：C/C++

>>19-22
判定：C
理由：
問題自体が難しすぎる。やさしい題材でもキラリと輝く出題が求められているのだ。
問題を難しくするだけなら馬鹿でもできる。最近では出色の >>12 を参考にし給え。

今日の釣堀
http://itpro.nikkeib...her/20130331/467401/

>>23

>>12 の意味が不明なのですが。2,3,4...はどうなるのですか？

まちがえました。 2,4,6,...はどうなるのですか？

>>12
999は3の倍数なのにどうして"Fizz"にならないのだろう

>>27
多分元の出題者のミスだろうね

>>23
意味不明の>>12のどこが出色なのか？

>>29
>>23 はマ板起源でム板で引用されたもの
ruby を想定した出題、記述もruby流、「ruby はこんなにすごいんだぞ！こんな問題もできないならOOと名乗るな＞C++, Java, その他もろもろ」的な
この出題者の意図はともかく、別の面でのこの問題の秀逸さに触発されてム板ではJava, C++ をはじめいろいろなので回答がついたマ板はいったことないからどうなったかしらない

どうぶつしょうぎの完全解。

http://joshi-shogi.c...sushogi/imgs/top.jpg
二人であそぶゲームです｡
はじめは盤の上に､図のようにどうぶつたちを並べます｡
http://joshi-shogi.c...hogi/imgs/shokei.gif
<うごかしかた>
それぞれ点がかいてある方向に一歩すすめます｡
百獣の王ライオンはどうぶつたちのリーダー｡
http://joshi-shogi.c...ushogi/imgs/lion.gif
たよりがいのあるぞうはナナメにすすめます｡
http://joshi-shogi.c...tsushogi/imgs/zo.gif
首の長いきりんはタテヨコにすすめます｡
http://joshi-shogi.c...shogi/imgs/kirin.gif
ちっちゃなひよこは前に一歩だけすすめます｡でも､成長すると?
http://joshi-shogi.c...ushogi/imgs/piyo.gif
ひよこが相手の一段目の空や森まですすむと､駒をひっくり返してニワトリに成長! ナナメ後ろ以外のマスにすすめます｡
http://joshi-shogi.c...gi/imgs/niwatori.gif
･相手のどうぶつがいるマスに自分の仲間がすすむときは､そのどうぶつをつかまえて仲間にできます｡つかまえたどうぶつは持ち駒にできます。
･持ち駒は､自分の番のときに､空いている好きなマスに置けます｡
<かちまけ>
1. 相手の｢ライオン｣を先につかまえたほうが勝ち!!
2. 自分の｢ライオン｣が､相手のエリア(空か森)まで先にすすめたら勝ち!! ただし､すすめてもすぐに｢ライオン｣がつかまってしまう場合は負けです｡
http://www.joshi-sho...butsushogi/rule.html

TILE GAMEの完全解。

http://www.vector.co...s/game/se004130.html
ルール
３ｘ３（あるいは４ｘ４など）の盤上で遊ぶオリジナルゲームです。
1.勝敗
盤面の空いたところに交互に自分の色のタイルを置き、向かい合った自分の辺と辺を、先に連絡した方が勝ちです。空いたところならどこに打ってもかまいません。
　□□□
■・・・■ ←３ｘ３の・の位置に交互にタイルを置く
■・・・■
■・・・■
　□□□
「連絡する」とは、タイルの辺が縦・横に接した状態にすることです。斜めに並んでいても連絡したことになりません。
　□□□
■　　□■
■■■■■ これは■が連絡しています。（■の勝ち）
■　□　■
　□□□

　□□□
■□■■■ これは□が連絡しています。（□の勝ち）
■□□　■
■　□　■
　□□□
2.「切り違え」ると、相手のタイルを取り除く
■□
□・←
上のような状態で、■が・の場所に、斜めに並んだ相手のタイルを切るように打つ（切り違える）と、□の２枚は盤上から取り除かれます。
■□■
□・□
上のような状態では、■が・の場所に打つと、□の３枚が除かれます。
3.パスはできない

http://toro.2ch.net/.../tech/1333801607/254　からの流れね

>>31
いくら成り金を組み入れたかったとはいえ、こんな狭い盤面での「にわとり」は最強すぎる‥‥

>>31
ちょっと調べてみたけどこんな小さな盤面でも78手もかかるんだな。

>>35
で「にわとり」の最強度はどれくらいです？やっぱり盤面全体を制圧するくらいの威力ですかね？

http://i.imgur.com/ufZXsbn.jpg

>>35
どうやって調べた？

test

なんかないですか

[1] 授業単元名：DDoS攻撃 v.s. パケットフィルタ
[2] 問題文：非負の整数が標準入力から100億個程与えられるものとする。
この時、100万回以上出現する値をできるだけ多く出力せよ。
但し、これに以下の条件を加えるものとする。
・入力の細かい形式や分布等は適切に仮定すること。
・入力される値のサイズは、その言語や環境で快適に扱える程度である(例えば64bitに十分収まるもの)と仮定しても良い。
[3] 環境
　[3.1] OS：指定なし
　[3.2] コンパイラ名とバージョン：指定なし
　[3.3] 言語：指定なし

もうC/C++の居場所なんてどこにもないんだね。。。（´・ω・`）

むずかしい

非負の整数の上限は？

limit.hとかにデファインがあったね

>>44

unsigned なら簡単
(unsigned)-1 で良い

signed は難しい
多くの場合は (int)((unsigned)-1/2) で良いが、そうじゃない環境も存在する
全数検索で最大を探すのにもトラップ値が問題となる
だれか方法知ってる？

~(1<<(sizeof(int)*8-1))
じゃ駄目なのか？

>>47
全然ダメ
まだ >>46 の方がマシ

負の数が2の補数じゃない環境 (1の補数や符号ビット)
charが8bitじゃない環境 (charが16bitとか)
intがcharの整数倍じゃない環境（パディング付き）
シフトで非負整数の範囲を超える数は未定義

チューリング賞ﾏﾀﾞｧ?(・∀・ )っ/凵⌒☆ﾁﾝﾁﾝ