体調もやる気も
このやる気はフィクションであり、実在の人物・団体・事件などとは一切関係ありません < dankogaiのやる気スイッチは幻想でした。 http://shindanmaker.com/14342 #yaruki
というありさまなので、リハビリ代わりに
の最後の問題をiMacに解かせてみた
問題7
5×5のマス目に6個の○を次の条件を満たすように書きます。条件:各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。
このとき、6個の○を書く方法は全部で何通りありますか。
これを何も考えずCに直訳したのが以下。
5x5x6.c#include <stdlib.h> #include <stdio.h> #define printit(a,b,c,d,e,f) printf("%02d,%02d,%02d,%02d,%02d,%02d\n",\ a,b,c,d,e,f) int main(void){ char rows[5], cols[5]; int a, b, c, d, e, f, i, p = 0, t = 0; for (i = 0; i < 5; i++) rows[i] = cols[i] = 0; /* init */ for (a = 0; a < 25; a++){ rows[a % 5]++; cols[a / 5]++; for (b = 0; b < 25; b++){ if (a == b) continue; rows[b % 5]++; cols[b / 5]++; for (c = 0; c < 25; c++){ if (a == c) continue; if (b == c) continue; rows[c % 5]++; cols[c / 5]++; for (d = 0; d < 25; d++){ if (a == d) continue; if (b == d) continue; if (c == d) continue; rows[d % 5]++; cols[d / 5]++; for (e = 0; e < 25; e++){ if (a == e) continue; if (b == e) continue; if (c == e) continue; if (d == e) continue; rows[e % 5]++; cols[e / 5]++; for (f = 0; f < 25; f++){ if (a == f) continue; if (b == f) continue; if (c == f) continue; if (d == f) continue; if (e == f) continue; rows[f % 5]++; cols[f / 5]++; t++; if( rows[0] && cols[0] && rows[1] && cols[1] && rows[2] && cols[2] && rows[3] && cols[3] && rows[4] && cols[4] ) { printit(a,b,c,d,e,f); p++; } rows[f % 5]--; cols[f / 5]--; } rows[e % 5]--; cols[e / 5]--; } rows[d % 5]--; cols[d / 5]--; } rows[c % 5]--; cols[c / 5]--; } rows[b % 5]--; cols[b / 5]--; } rows[a % 5]--; cols[a / 5]--; } fprintf(stderr, "%d / %d\n", p, t); return 0; }
こんな力押しコードに20分も罹って、大丈夫か?
しかもこれ、例えば(00,06,12,18,24,01)と(01,06,12,18,24,00)を別カウントしているので、○をそれぞれ別ものとして扱った場合は正しいのだろうけど、問題を見る限りこういう場合は同一視しなければならなさそう。とすると、3,024,000を6! = 720 で割った 4,200が正解ということかな?
この場合の全組み合わせは、上のstdoutをさらに以下のperl scriptに食わせれば出る。
5x5x6-pp.pl#!/usr/bin/env perl use 5.010; use strict; use warnings; my %dupe; while(<>){ chomp; $dupe{ join ",", sort split /,/, $_ }++ }; say for sort keys %dupe;
こんだけ力押ししても、Core i7なiMacでは実行はこんなもん。
% gcc -W -Wall -O6 5x5x6.c % /usr/bin/time -l ./a.out >! 5x5x6.out 3024000 / 127512000 3.68 real 3.15 user 0.14 sys 0 maximum resident set size 0 average shared memory size 0 average unshared data size 0 average unshared stack size 0 page reclaims 0 page faults 0 swaps 1007 block input operations 1 block output operations 0 messages sent 0 messages received 0 signals received 1025 voluntary context switches 0 involuntary context switches % wc 5x5x6.out 3024000 3024000 54432000 5x5x6.out % perl 5x5x6-pp.pl 5x5x6.out |wc 4200 4200 75600
- 6重ループってなにこれきもい
- continueの使い方とかコピペ濫用にもほどがある。
- それでも一応問題の見積もりはしている。チェックすべき組み合わせは 25P6 = 127,512,000。この時点でCで書くことを決定。
- キモいループが正しくまわっているかどうかを、一応ループカウントしてチェック。確かに127512000と出ている。
- アンチョコは一切見ていない。「エレガントな問題解決」に似たような問題が出ていたような気はするのだけど…
なんて書いておくと、MacBook Airくれるのかしらん…
Dan the Brute Forcer
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。