人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【プログラム クイズ】
「孤独の7」を解くプログラムを書いてみてください。


※答えが出るまでの時間と実行したマシンスペックも教えてください。


・「孤独の7」
http://yosshy.sansu.org/lonely7.htm

1297128814
●拡大する

●質問者: garyo
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:クイズ スペック プログラム マシン 孤独
○ 状態 :終了
└ 回答数 : 5/5件

▽最新の回答へ

1 ● SALINGER
●20ポイント

普通にVBAでの総当りです。

Corei7 870 2.93GHzで10秒弱。


考え方としては、ヒントの7と各式の桁数を満たさなければ次の数値を試すというやり方。

同じようなコードで入れ子になってるので再帰を使えばすっきりしそうです。

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
◎質問者からの返答

ありがとうございます。

最近のPCだと総当りでも10秒程度で解けてしまうのですね。


2 ● ootatmt
●20ポイント

総当りのコード(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
◎質問者からの返答

ありがとうございます。

2数を総当りで、途中計算を桁数で絞り込むわけですね。


3 ● imo758
●20ポイント

http://codepad.org/dv7SypOd

codepad.orgのスペックはわかりませんが

Windows XP メインメモリ512Mセレロン1.1GHzで

だいたい1回解くのに平均0.91/sとでました

自明な場合をいくつか省いていますが

もっと愚直なアルゴリズムのほうがよろしかったでしょうか?

◎質問者からの返答

ありがとうございます。

codepadは面白いですね。何かこれを使った質問ができると面白いかも。


4 ● グラ娘。
●20ポイント

Visual C++ 2008 Express Editionで作ったコンソール?アプリです。(ほぼC言語。)

マイコンピュータのプロパティにはMobile AMD Sempron(tm) Processor 3200+ 1.60GHz、960MB RAM と書いてあります。

かかる時間はわかりません。時間計測の方法があってれば1ms以下だと思いますが起動に1.5秒ほどかかってる?

// 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ほどになりました。

覆面算というやつには対応してなかったので途中で止めました。

◎質問者からの返答

ありがとうございます。

やはりスクリプトよりネイティブアプリの方が早そうですね。


5 ● rsc
●20ポイント

割り算の形から、c=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);
}
◎質問者からの返答

ありがとうございます。

http://q.hatena.ne.jp/1296542184

こちらの質問をみて私も同じ問題に対して、色々な方が書かれるプログラムを読んで見たくなり質問してみました。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ