【プログラム クイズ】
「孤独の７」を解くプログラムを書いてみてください。
※答えが出るまでの時間と実行したマシンスペックも教えてください。
・「孤独の７」
http://yosshy.sansu.org/lonely7.htm
No.1
3454
969
20pt
普通にVBAでの総当りです。
Corei7 870 2.93GHzで１０秒弱。
考え方としては、ヒントの７と各式の桁数を満たさなければ次の数値を試すというやり方。
同じようなコードで入れ子になってるので再帰を使えばすっきりしそうです。
Sub Macro() Dim i As Long Dim j As Long Dim k As Long Dim l As Long For i = 10000 To 99999 If Mid(i, 2, 1) = "7" Then For j = 100 To 999 k = i * j If k >= 10 ^ 7 Then l = Mid(i, 1, 1) * j * 10 ^ 4 If l >= 10 ^ 7 And l < 10 ^ 8 Then k = k - l If k >= 10 ^ 5 And k < 10 ^ 6 Then l = Mid(i, 2, 1) * j * 10 ^ 3 If l >= 10 ^ 5 And l < 10 ^ 6 Then k = k - l If k >= 10 ^ 5 And k < 10 ^ 6 Then l = Mid(i, 3, 1) * j * 10 ^ 2 If l >= 10 ^ 4 And l < 10 ^ 5 Then k = k - l If k >= 10 ^ 3 And k < 10 ^ 4 Then l = Mid(i, 4, 1) * j * 10 If l = 0 Then k = k - l If k >= 10 ^ 3 And k < 10 ^ 4 Then l = Mid(i, 5, 1) * j If l >= 10 ^ 3 And l < 10 ^ 4 Then Debug.Print i & vbNewLine & j End If End If End If End If End If End If End If End If End If End If Next j End If Next i End Sub
No.2
130765
20pt
総当りのコード(VBA)です。
AMD Phenom X4 9350e で 2秒ぐらいかかりました。
もうちょっときれいに書けば早くなるかもしれません。
Option Explicit Sub 虫食い算() Dim a As Long Dim a321 As Long Dim a5 As Long Dim b As Long Dim c As Long Dim t1 As Long Dim t2 As Long Dim t3 As Long Dim t4 As Long Dim t5 As Long Dim t6 As Long Dim t7 As Long Dim myTime myTime = Time For a5 = 1 To 9 For a321 = 0 To 999 ' 商は、1000の位が7である5桁の数字を総当り a = a5 * 10000 + 7000 + a321 ' 割る数も総当り For b = 100 To 999 c = a * b If c >= 10000000 Then t1 = a5 * b If t1 >= 1000 And t1 <= 9999 Then t2 = Int(c / 10000) - t1 If t2 >= 10 And t2 <= 99 Then t2 = t2 * 10 + Mid(c, 5, 1) t3 = b * 7 t4 = t2 - t3 If t4 >= 100 And t4 <= 899 Then t4 = t4 * 10 + Mid(c, 6, 1) t5 = Int(a321 / 100) * b If t5 >= 100 And t5 <= 999 Then t6 = t4 - t5 If t6 >= 10 And t6 <= 99 Then t6 = t6 * 10 + Mid(c, 7, 1) If t6 < b Then t6 = t6 * 10 + Mid(c, 8, 1) t7 = b * (a321 Mod 100) If t6 = t7 Then Debug.Print c & " / " & b & " = " & a End If End If End If End If End If End If End If End If Next Next Next Debug.Print (Time - myTime) * 3600 * 24 End Sub
ありがとうございます。
２数を総当りで、途中計算を桁数で絞り込むわけですね。
No.3
12119
20pt
codepad.orgのスペックはわかりませんが
Windows XP メインメモリ512Mセレロン1.1GHzで
だいたい１回解くのに平均0.91/sとでました
自明な場合をいくつか省いていますが
もっと愚直なアルゴリズムのほうがよろしかったでしょうか？
ありがとうございます。
codepadは面白いですね。何かこれを使った質問ができると面白いかも。
No.4
560170
20pt
Visual C++ 2008 Express Editionで作ったコンソール？アプリです。（ほぼC言語。）
マイコンピュータのプロパティにはMobile AMD Sempron(tm) Processor 3200+ 1.60GHz、960MB RAM と書いてあります。
かかる時間はわかりません。時間計測の方法があってれば1ms以下だと思いますが起動に1.5秒ほどかかってる？
549
524
// kodoku7.cpp : メイン プロジェクト ファイルです。
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"
using namespace System;
bool kenzan(int sho,int josu){
int hijo = sho*josu;
int amari = 0;
amari = hijo - josu*((sho/10000)*10000);
if ( amari > 999999 || amari < 100000) return false;
amari = hijo - josu*((sho/1000)*1000);
if ( amari > 999999 || amari < 100000) return false;
amari = hijo - josu*((sho/100)*100);
if ( amari > 9999 || amari < 1000) return false;
amari = hijo - josu*((sho/10)*10);
if ( amari > 9999 || amari < 1000) return false;
if ( hijo - josu*sho == 0) return true;
return false;
}
int main(array<System::String ^> ^args)
{
clock_t in,out;
in = clock();
//かいし
printf("start\n");
int sho,jo;
for(int i1=1;i1<=9;i1++){
for(int i2=0;i2<=9;i2++){
for(int i3=0;i3<=9;i3++){
jo = i1*100 + i2*10 + i3;
for(int j1=1;j1<=9;j1++){
if ( (j1*jo)<1000 || (j1*jo)>9999)continue;
if ( (7*jo)<100 || (7*jo)>999 )continue;
for(int j2=0;j2<=9;j2++){
if ( (j2*jo)<100 || (j2*jo)>999 )continue;
for(int j3=0;j3<=9;j3++){
//ここが0なのは私の入れ知恵
if ( (j3*jo)!=0 )continue;
for(int j4=0;j4<=9;j4++){
if ( (j4*jo)<1000 || (j4*jo)>9999)continue;
sho=j1*10000 + 7000 + j2*100 + j3*10 + j4;
if(sho*jo > 99999999 || sho*jo <10000000)continue;
if (kenzan(sho,jo)){
printf("%d ÷ %d ＝ %d・・・0\n",sho*jo,jo,sho);
}
}
}
}
}
}
}
}
//おしまい
out = clock();
printf("%.3f秒\n",(double)(out-in)/CLOCKS_PER_SEC);
printf("start %d end %d\n",in,out);
int c = getchar();
return 0;
}
実行結果
start
12128316 ÷ 124 ＝ 97809・・・0
0.000秒
start 1406 end 1406
このあと、他の虫食い算でも動くように作り変えたら実行時間が50msほどになりました。
覆面算というやつには対応してなかったので途中で止めました。
ありがとうございます。
やはりスクリプトよりネイティブアプリの方が早そうですね。
No.5
4497436
20pt
割り算の形から、ｃ＝0は既知としました。それから、割る数は7との掛け算が3桁となるから百の位を1としました。計算途中の掛け算と余りの桁数でチェックして消去法でクリアしたものを出力するようにしました。
即席で、ネットで調べてないので見苦しいソースです。(^_^;
実行時間は、0.3[sec]で、マシンスペックは、プロセッサ：Intel(R)Core(TM)2 Duo CPU E4500 @2.20GHz 1.10GHzです。(^_^;
コンパイルは、「Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland」を使いました。_dos_gettime()を使っているので、「古い形式」と警告が出ますが使えるみたいです.(^_^;
/* lone7.c */ #include <stdio.h> #include <string.h> #include <dos.h> long dtimer(void) /* 「古い形式」と警告が出ますが使えるみたいです.(^_^; */ { struct dostime_t dt; int h,m,s,hs; _dos_gettime(&dt); h =dt.hour, m =dt.minute, s =dt.second, hs=dt.hsecond; return(360000L*h+6000L*m+100L*s+hs); } /* 桁数を求める関数 */ int check_keta(int x) { char buf[32]; sprintf(buf,"%d",x); return(strlen(buf)); } int main(void) { int dvd; /* 元の割られる数 dividend */ int quo; /* 商 quotient */ int div; /* 割る数 divisor */ int rem; /* 計算途中の余り remainder */ int tmp; /* 計算途中の割られる数 */ int a,b,c=0,d; /* 商の各桁 c=0は形から既知としました。(^_^; */ long t0,dt; t0=dtimer(); /* タイマースタート */ for(div=100; div<200; div++){ /* 割る数の百の位は1 */ for(a=1; a<10; a++){ /* 商の先頭は、0以外の数 */ for(b=0; b<10; b++){ for(d=0; d<10; d++){ quo=10000*a+1000*7+100*b+10*c+d; dvd=quo*div; if(check_keta(div*a)!=4) continue; /* 消去法でスキップ */ tmp=dvd/10000; rem=tmp%div; if(check_keta(rem)!=2) continue; if(check_keta(div*7)!=3) continue; tmp=rem*10+(dvd/1000)%10; rem=tmp%div; if(check_keta(rem)!=3) continue; if(check_keta(div*b)!=3) continue; tmp=rem*10+(dvd/100)%10; rem=tmp%div; if(check_keta(rem)!=2) continue; tmp=rem*10+(dvd/10)%10; rem=tmp%div; if(rem!=tmp) continue; printf("%d / %d = %d%d%d%d%d\n",dvd,div,a,7,b,c,d); } } } } dt=dtimer()-t0; /* タイマーストップ */ printf("Runtime : %ld.%ld [sec]\n",dt/100,dt%100); return(0); }
ootatmt
2011/02/09 09:17:47
1
1
2
3
2
1
1
SALINGER
garyo
imo758
rsc
ありがとうございます。
最近のPCだと総当りでも１０秒程度で解けてしまうのですね。