トップページ⇒tech
621コメント167KB

いっしょにプログラムを作ってくれる方募集

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
どなたか一緒にプログラムを作りませんか？
開発言語はＣ言語です。
開発するものは、クイックソートとマージソートです。
いっしょに作ってくれる方はレスをつけてください。
0571デフォルトの名無しさんNGNG
わしはP-MMX/233(古!)でN=40で 45秒ほど。おそいのう。

ところで
>>546
よーわからんのだが、全体を足したってことかの？
0572508NGNG
クルーソー533MHｚで（この時点で比較できないような(＾＾;)
鏡像除去済み（のつもり）

N=3〜N=40までサーチして50秒
N=39までで29秒・・・かな？
0573508NGNG
うわ、かなりおそいか(汗
0574デフォルトの名無しさんNGNG
N=40で4.5秒が出た！

n=40
Σdt(n) ではないです。
n=2

鏡像除いて590個なんですけど、あってます？
0575568NGNG
574は568です。
0576508NGNG
デバッグビルドだった・・・
リリースで、39まで16秒、40まで27秒かな？
0577508NGNG
あり？64個だったよ・・・

32:1個
33:1個
34:11個
35:57個
0578568NGNG
う゛っ、最後の一個判定ミスってました。
訂正しますが、速度は変わらない…はず。
0579568NGNG
n=40で64個でしょうか。
0580508NGNG
>>568
たぶん、N=40で64個です

ところで、なんでそんなに速いの?
0581デフォルトの名無しさんNGNG
結局みんな、>>1に馬鹿にされたのが腹に据えかねてるのね。
0582デフォルトの名無しさんNGNG
このスレじゃなくて、「今月にＣマガパズル」とかスレ立てればいいのに。
0583568NGNG
う゛っ、またミス。枝きりのミスで
実際は２倍かかってしまいました。
なんで n=40 で 8.8[s] です。

4.5[s] なんて大見得切ったのに。鬱だ…。
0584508NGNG
>>581
ちがうよ、やってみたら面白かっただけだよ。

>>582
せっかくだからこのスレ使いきっちゃおうよ。

>>583
だとすると同じくらいかな？
0585デフォルトの名無しさんNGNG
>>581
腹に据えかねたやつはとっとと逃げたか影でコソコソしとるだけ
じゃろ。
0586デフォルトの名無しさんNGNG
N=45だと21931通り？
P3-866MHzでN=1-45まで順に求めて77.36秒でした。
N=1-40までだと0.47秒くらい。
05871NGNG
>>586
0.47秒ですか。すごいですね。できればどんな枝切りしたか
教えてほしいです。
0588508NGNG
45まで出すのに一時間かかっても終わりません(笑
とりあえず、44は10091個だったよ・・・・。
05891NGNG
>>588
同じく、45は長すぎるので途中でやめました。44は10091です。
何かしらの判定方法があるんでしょうがそれを見つけないと
これ以上のスピードアップは難しいですね。
05901NGNG
同じくVCのリリースでビルドしたらスピードがあがった。
N=40で7.781秒
N=1からN=40までで、18.536秒でした。586には程遠い。
0591デフォルトの名無しさんNGNG
プログラムの書き方を工夫したら少し速くなりました。
N=1-45で36.66秒でした。
答え、合ってるのかなぁ。

一日無駄にしちゃったよ。ちょっと鬱な気がする。
0592268NGNG
>1
へろー
おもしろいことやってるね。

おれも作ってみたんだけど、
誰かソース見てくれません？
これでいいのかわかんないんで。
05931NGNG
>>591
どうゆう枝切りしたの？教えてください。
05941NGNG
>>268
とりあえず答え上げていけば正しいかどうかわかるよ。
591の結果とくらべて差がありすぎるので
もうちょっとソースはもっと改良してから上げます。
0595268NGNG
>1
それが、最小のnしか求められないんだよ・・・
だから見てほしいんだ。
許可でたらbase64で貼っつけるよ。
0596デフォルトの名無しさんNGNG
アプロダ使えば？
0597268NGNG

http://wqbodnpt.tripod.com/
上げといた。
0598268NGNG
ついでにいうと、
その数の一番はじめに見つかった組み合わせだけ表示するようにした。
0599508NGNG
>>598
組み合わせが見つかったとき、つまり再帰で最後まで届いたときに
見つからなかったことにすれば続き探してくれるよ
06001NGNG
>>268
ちょっと変わったプログラムですね。はっきりとあってるかどうかわからなかった。

とりあえずグローバル変数は最初から０で初期化されてるので０初期化は不要です。

それからすでに使われてる数の判定するPopUseもちょっと。
ふつうにiがつかわれてるときはlist[i] = 1;で使われてないときは
list[i] = 0;だけで判定したほうがわかりやすくていいと思います。

平方数判定はテーブルを作って
char ntable[MAX_NUM*2];//ntableは０で初期化して。
for(i = 1;i <= MAX_NUM;i++) {
　if(i * i > 2 * MAX_NUM) break;
　ntable[i*i] = 1;
}
ってして、aを判定するときntable[a] == 1なら平方数って判定できます。
この方がずっと早くてプログラムも簡単になります。

あとfunc1のmaxをポインタで渡しても意味がないので
やめた方がいいかと。
06011NGNG
597のプログラムを修正しました。

#include<stdio.h>

#define MAX_NUM 96

char list[MAX_NUM]; /* 使われているかチェックするときに使う配列 */
int chain_ring[MAX_NUM]; /* 解を入れておく */
int flag; /* 終了判定フラグ　兼　カウンター */

int sqrl[MAX_NUM * 2];
/* init: 初期化 */
void init(){
int i = 1;
while( i * i < MAX_NUM * 2){
sqrl[i*i] = 1;
i++;
}
}

/* func1: 全検索関数。再帰によって行う。メイン処理 */
void func1(int max ,int ip ){
int i;

if( ip >= max ){
if( sqrl[chain_ring[ip-1] + chain_ring[0]]){
for(i = 0;i < max;i++)
printf("%d ",chain_ring[i]);
printf("\n");
flag++;
}
return;
}

for( i = 2; i <= max; i++ ){
if ( !list[i] ){ /* iが使われてないとき */
if( sqrl[ i + chain_ring[ip-1]] ){
list[i] = 1;
chain_ring[ip] = i;
func1(max,ip+1);
list[i] = 0;
}
}
}
}
06021NGNG
続きです。

/* main */
int main( void ){

int max;
init();

for( max = 2; max < MAX_NUM; max++ ){
printf("max = %3d.. ",max );
/* 最初を１で固定することで、回転した解がでないようにする*/
chain_ring[0] = 1;
list[1] = 1;
func1(max ,1);
if( flag ){
printf( "I do it!\n hit n=%d!\n",max,flag/2 );
break;
}

printf( " done... \n" );
}

return 0;
}

/* EOF */
0603508NGNG
遅くなったっす
P3-１GHzでN=3〜45で
2691秒=44分51秒(爆)

で、たしかに21931個のようです
0604268NGNG
遅くなったっす。
モデムのデバイスふっとびました。
原因は不明・・・
自分のプログラムを起動中にFTPソフト終わらせたらふっとびました・・・
あ、そんなことはどうでもいいか・・・

>1
なるほど。
できるだけ計算をなくすようにすればいいのか・・・
勉強になります。
(つーかこのアルゴリズムって役に立つんだろうか・・・)

後はできるだけ削るだけかな？
06051NGNG
おはようございます。N=46を求めました。69623です。
74分もかかりました。

>>604
テーブルを作って判定する、って方法などはいろんなところで使われてるので
覚えてそんはないと思います。
後はとりあえず鏡像になる計算を省くために、562で書いたことをやってみてください。
0606デフォルトの名無しさんNGNG
>>605
たぶん合ってます。N=50まで計算しました。

N=46　69623
N=47　115913
N=48　227893
N=49　457707
N=50　297126

N=50までの計算で21分でした。
0607508NGNG
>>606
ちょっとやそっとの差じゃないよね(^^;
どうやってやってるんだろう??
06081NGNG
>>606
詳細希望。すごすぎです。
0609デフォルトの名無しさんNGNG
真面目なスレになったら廃れたから
やはり>>1叩きで行こうYO!
06101NGNG
>>606
できれば６０まで求めて、アップしてもらえませんか。
0611課題読書感想文NGNG
あらららら・・・
>>1のとこに、
>いっしょに作ってくれる方はレスをつけてください。

>>2-610 まで、
延べ609人の共同制作者がいるじゃん？　ネタスレに終わるかと思ってたら
後半はマジレスの嵐じゃん。

2chって凄い！　感動した!!!
0612デフォルトの名無しさんNGNG
定期age
0613デフォルトの名無しさんNGNG
http://homepage2.nifty.com/katuya/index.html
0614508NGNG
ごめん、もうギブアップ･･･
606の解説および次の問題待ち・・・
0615デフォルトの名無しさんNGNG
分りにくいので、やっぱ新スレ建ててください＞１
06161NGNG
>>615
とりあえずもう１問ぐらいはこのスレで。
Ｃマガの過去問でもいいのかな？
だれか問題あったらだして。
0617デフォルトの名無しさんNGNG
N=50: 297126 (5分43秒)
N=51: 1051583 (12分18秒)
N=52: 3377189 (29分12秒)
N=53: 7618873 (1時間6分36秒)
N=54: 12476654 (2時間28分26秒)
N=55: 25832098 (5時間19分57秒)
N=56: 55792448 (11時間46分20秒)
N=57: 75126741 (21時間19分37秒)
N=58: 129180538 (41時間25分41秒)

時間はN=1からの累計です。
ほぼ倍々に増えているので、N=60まではあと5日くらいかな。
0618デフォルトの名無しさんNGNG
ちなみに、N=50までの時間が606と違うのは、プログラムを工夫して速くしたからです。

解き方（それほど賢いアルゴリズムではないけど）
{1, 2, ..., N}を頂点、和が平方数になる2数を辺とするグラフを作る。
頂点Nから出発。（回転を除去）
頂点Nとつながってる頂点を2つ選ぶ。大きい方をS,小さい方をEとする。（鏡像を除去）
グラフから頂点Nと、頂点Nにつながる辺を外す。
このグラフの上で、SからEまで全部の点を一度ずつ通ってたどり着けばいい。

Sとつながってる頂点を1つ選んで、S'とする。そういう頂点がなければ、進めないから失敗。
グラフから、頂点Sと、Sにつながっている辺を外す。
ここで、S'とE以外に「辺が1本しかない頂点」ができたら、もう無理。（枝苅り）
S'からEまで行けるか調べる（再帰）

S=Eになったとき、グラフの頂点がEだけだったら解。
Eの他に頂点があれば、通ってないので駄目。
0619508NGNG
>>617
ごめん、頭悪いかも････

頑張って解読します・・・。
0620デフォルトの名無しさんNGNG
>ここで、S'とE以外に「辺が1本しかない頂点」ができたら、もう無理。（枝苅り）

の枝刈(苅?)が効くんですかね〜。違うところはここだけなんだが。
グラフ的に解く方法は思いついたんですが、こんなに速くなると
は思わなかったです。やはり枝刈は大切か。
0621508NGNG
なるほど、最初に道を全部洗い出してから一筆書きするんですね。
で、行き止まりに当たる可能性を先の分まで調べてしまう、ってことですね。

僕の場合は行き当たりばったりで道を探すから遅かった、ってとこかな。
■ このスレッドは過去ログ倉庫に格納されています