暇な香具師は問題に挑戦スレ(ネタバレ厳禁)
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
NGNG上手い方法がありそうで、なかなか見つからない
そんな挑戦するに値する難問奇問を保存・収集するスレです
もし他のスレで良い問題あったら、どんどん紹介して下さい
もちろんオリジナルやネット上で見つけたもの何でもOKです
なお解き方が分かってもヒントや答えは絶対に書かないで下さい
注意
１ 基本的には各種言語に依存しないアルゴリズムの問題を対象とします
２ １に該当しなくても面白そうならばOK
３ 答えやヒントの書きこみは禁止ですがリンクを貼るのはOK
４ 答えが分かってなくても解けそうな気がするものは大歓迎
５ ですが明らかに答が無い問題(力技等)は対象外
６ ここは宿題スレではないので答を期待して書きこまないで下さい
00021(例題１)
NGNGC/C++の宿題をやらせろや!!!スレより(表現を一部変えてあります)
２分割（反転や回転も考慮）するプログラムを作成しなさい。
'-'は空白を表します
また、縦と横の比が違うので分かり辛いですが
'#'と'$'で構成された図形は回転させれば同じ図形です
例題：
*******
*******
**----*
**----*
****--*
****--*
------*
------*
解答：
####### -------
#------ -$$$$$$
#------ -$----$
#------ -$----$
#--#--- -$$---$
####--- ------$
------- ------$
------- ------$
00032(例題２)
NGNG画像処理スレより (そのまま転載)
俺が大学生だったときにめちゃくちゃ頭の良い友達に出題されて
結局解けなかった問題をここに挙げます。
横wピクセル、縦hピクセルの画像がある。この画像を９０度回転せよ。
ただし、ピクセルの移動に使う記憶領域はaピクセル分しか使ってはならない。
また元の画像が保存されている記憶領域上に計算結果が得られるとする。
１．上の問題を a = w × h の条件で解くアルゴリズムを考案せよ。
２．同じく、a で w × h が割り切れるような a の場合でのアルゴリズムを考案せよ。
３．同じく、a = 1 でのアルゴリズムを考案せよ。
４．任意の a についてのアルゴリズムを考案せよ。
５．１から４でもしアルゴリズムが存在しない場合があるなら、その条件を明らかにせよ。
６．１から４でピクセルの移動についての計算量を求めよ。
１については超簡単で、計算量は 2wh (h × w のバッファに画像を回転させながら
移動し、全部終わったらもとに戻す)になると思いますが、あとは解りませんでした。
00041
NGNG暇な香具師が、挑戦するスレ(何度も書くけど解答の書き込み禁止)です
0005デフォルトの名無しさん
NGNG90度回転して元の画像に上書きするのに縦と横の長さが違うのは何でやねん
3 ならわかったが、それが十分に効率的なので 1,2,4 の存在価値がわからん
0006デフォルトの名無しさん
NGNGhttp://pc2.2ch.net/test/read.cgi/tech/992671330/199
> ごめん。もうひとつ重要な条件を忘れていた。
>
> ピクセルを移動するときは、必ずaの記憶領域を通さなければならない。
>
> 直接移動はダメということです。
たぶん直接移動は禁止みたいな条件があるんじゃないかと思って、
画像処理スレを読んだら、やっぱりあった。
0007デフォルトの名無しさん
NGNGそれは出題がクソだ・・・直接移動を禁止する意義がわからん。
0008デフォルトの名無しさん
NGNG画像が格納されている記憶領域をメモリ、
aの記憶領域をレジスタと考えれば、
メモリ→メモリの命令がなくて、
メモリ→レジスタ、レジスタ→メモリの命令があるような
CPUを使って回転させるって問題に置き換えられる。
意義がないわけではではないと思う。
0009デフォルトの名無しさん
NGNG0011デフォルトの名無しさん
NGNGそんな、激しく非現実のネタで出題者を擁護しなくたっていいんじゃないか？
00128
NGNGそんなに非現実でもないと思うけど。
0013デフォルトの名無しさん
NGNG0014デフォルトの名無しさん
NGNG普通スタックくらい使えるし、ダメなら画像回転なんかやってる余裕ないはず。
00158
NGNGできるだけ移動回数を減らそうという問題なんだから
スタック使って移動回数増やしてどうする。
0016デフォルトの名無しさん
NGNGつーか、a = 1 じゃあ回転の前に移動が不可能だろ。
0018デフォルトの名無しさん
NGNG移動は可能、ほほう。
じゃあ、w = 2、h = 1、a = 1 の条件で 2 つのピクセルを入れ替えてみてくれ。
00198
NGNG0020デフォルトの名無しさん
NGNG少しは頭使いなさいよ。
ピクセルが 2 つしかなくて、それぞれを移動させるなら入れ替えになるでしょ。
00218
NGNG当然消してしまうんで回転は不可能って考えたんだけど。
屁理屈のようなものなんだろうか。
消しちゃだめなら、確かに移動は不可能。
0022デフォルトの名無しさん
NGNGw = 1、h = 1 の場合を除いて。
0023デフォルトの名無しさん
NGNG00241
NGNGhttp://pc2.2ch.net/test/read.cgi/tech/992671330/199
を無視しても、それなりに面白いと思うし
後付けの条件を含めても５の条件があるから
そのままでも良いと思ったのですが
こちらの問題も手直しした方が良かったのかな…
0025デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています