5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

暇な香具師は問題に挑戦スレ(ネタバレ厳禁)

1 :デフォルトの名無しさん:03/01/29 05:53
このスレは今まで各スレにあった解けそうで解けない
上手い方法がありそうで、なかなか見つからない
そんな挑戦するに値する難問奇問を保存・収集するスレです
もし他のスレで良い問題あったら、どんどん紹介して下さい
もちろんオリジナルやネット上で見つけたもの何でもOKです
なお解き方が分かってもヒントや答えは絶対に書かないで下さい

注意
1 基本的には各種言語に依存しないアルゴリズムの問題を対象とします
2 1に該当しなくても面白そうならばOK
3 答えやヒントの書きこみは禁止ですがリンクを貼るのはOK
4 答えが分かってなくても解けそうな気がするものは大歓迎
5 ですが明らかに答が無い問題(力技等)は対象外
6 ここは宿題スレではないので答を期待して書きこまないで下さい

2 :1(例題1):03/01/29 05:54
http://pc2.2ch.net/test/read.cgi/tech/1041992392/552
C/C++の宿題をやらせろや!!!スレより(表現を一部変えてあります)


2分割(反転や回転も考慮)するプログラムを作成しなさい。
  '-'は空白を表します
  また、縦と横の比が違うので分かり辛いですが
  '#'と'$'で構成された図形は回転させれば同じ図形です

例題:
*******
*******
**----*
**----*
****--*
****--*
------*
------*

解答:
####### -------
#------ -$$$$$$
#------ -$----$
#------ -$----$
#--#--- -$$---$
####--- ------$
------- ------$
------- ------$

3 :2(例題2):03/01/29 05:55
http://pc2.2ch.net/test/read.cgi/tech/992671330/192
画像処理スレより (そのまま転載)

俺が大学生だったときにめちゃくちゃ頭の良い友達に出題されて
結局解けなかった問題をここに挙げます。

横wピクセル、縦hピクセルの画像がある。この画像を90度回転せよ。
ただし、ピクセルの移動に使う記憶領域はaピクセル分しか使ってはならない。
また元の画像が保存されている記憶領域上に計算結果が得られるとする。
1.上の問題を a = w × h の条件で解くアルゴリズムを考案せよ。
2.同じく、a で w × h が割り切れるような a の場合でのアルゴリズムを考案せよ。
3.同じく、a = 1 でのアルゴリズムを考案せよ。
4.任意の a についてのアルゴリズムを考案せよ。
5.1から4でもしアルゴリズムが存在しない場合があるなら、その条件を明らかにせよ。
6.1から4でピクセルの移動についての計算量を求めよ。

1については超簡単で、計算量は 2wh (h × w のバッファに画像を回転させながら
移動し、全部終わったらもとに戻す)になると思いますが、あとは解りませんでした。

4 :1:03/01/29 05:56
以上、こんなような問題を集めて
暇な香具師が、挑戦するスレ(何度も書くけど解答の書き込み禁止)です

5 :デフォルトの名無しさん:03/01/29 13:27
>>3
90度回転して元の画像に上書きするのに縦と横の長さが違うのは何でやねん
3 ならわかったが、それが十分に効率的なので 1,2,4 の存在価値がわからん

6 :デフォルトの名無しさん:03/01/29 13:40
>>3
http://pc2.2ch.net/test/read.cgi/tech/992671330/199
> ごめん。もうひとつ重要な条件を忘れていた。
>
> ピクセルを移動するときは、必ずaの記憶領域を通さなければならない。
>
> 直接移動はダメということです。

たぶん直接移動は禁止みたいな条件があるんじゃないかと思って、
画像処理スレを読んだら、やっぱりあった。

7 :デフォルトの名無しさん:03/01/29 13:54
>>6
それは出題がクソだ・・・直接移動を禁止する意義がわからん。

8 :デフォルトの名無しさん:03/01/29 14:17
>>7
画像が格納されている記憶領域をメモリ、
aの記憶領域をレジスタと考えれば、
メモリ→メモリの命令がなくて、
メモリ→レジスタ、レジスタ→メモリの命令があるような
CPUを使って回転させるって問題に置き換えられる。

意義がないわけではではないと思う。

9 :デフォルトの名無しさん:03/01/30 06:36
a=1 しか実現できないほどレジスタが少ない CPU があるのか?

10 :8:03/01/30 13:04
>>9
他の計算に使ってしまっていて、aの記憶領域として使えるレジスタが
限られる場合はあると思うけど。

11 :デフォルトの名無しさん:03/01/30 14:38
画像の回転中に他の計算なんかするなよ。
そんな、激しく非現実のネタで出題者を擁護しなくたっていいんじゃないか?

12 :8:03/01/30 15:06
移動元、移動先の計算ぐらいはするでしょ。
そんなに非現実でもないと思うけど。

13 :デフォルトの名無しさん:03/01/30 20:52
直接移動は不可能として、aの領域とピクセルとの演算は許可されるのか?

14 :デフォルトの名無しさん:03/01/30 21:12
a=1 なんて環境はあり得ないだろ。
普通スタックくらい使えるし、ダメなら画像回転なんかやってる余裕ないはず。

15 :8:03/01/30 23:28
スタックも所詮メモリ。レジスタと同様には扱えない。
できるだけ移動回数を減らそうという問題なんだから
スタック使って移動回数増やしてどうする。

16 :デフォルトの名無しさん:03/01/30 23:57
移動回数を減らそう? え?

つーか、a = 1 じゃあ回転の前に移動が不可能だろ。

17 :8:03/01/31 01:33
>>16
移動は可能で、回転が不可能では。

>>3 では言外に計算量が「最少」のアルゴリズムを考案せよと
いっているのだと思ったが。

18 :デフォルトの名無しさん:03/01/31 01:42
>>17
移動は可能、ほほう。
じゃあ、w = 2、h = 1、a = 1 の条件で 2 つのピクセルを入れ替えてみてくれ。

19 :8:03/01/31 01:54
誰も入れ替えるとは言っていないが。

20 :デフォルトの名無しさん:03/01/31 02:05
>>19
少しは頭使いなさいよ。
ピクセルが 2 つしかなくて、それぞれを移動させるなら入れ替えになるでしょ。

21 :8:03/01/31 02:22
ピクセルを一つ消していいなら移動は可能。
当然消してしまうんで回転は不可能って考えたんだけど。
屁理屈のようなものなんだろうか。

消しちゃだめなら、確かに移動は不可能。

22 :デフォルトの名無しさん:03/01/31 02:28
つまり a は最低 2 って事か。
w = 1、h = 1 の場合を除いて。

23 :デフォルトの名無しさん:03/01/31 02:55
xorが可能ならa=1でもできないかな…

24 :1:03/01/31 02:56
>>3なんですが
http://pc2.2ch.net/test/read.cgi/tech/992671330/199
を無視しても、それなりに面白いと思うし
後付けの条件を含めても5の条件があるから
そのままでも良いと思ったのですが
こちらの問題も手直しした方が良かったのかな…

25 :デフォルトの名無しさん:03/01/31 03:16
つもりはなくても、徐々にネタバレに近づいている予感。

7 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)