1297128814 【プログラム クイズ】

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


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


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

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:2011/02/08 10:33:35
  • 終了:2011/02/15 10:40:19

回答(5件)

id:SALINGER No.1

SALINGER回答回数3454ベストアンサー獲得回数9692011/02/08 19:48:58

ポイント20pt

普通に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
id:garyo

ありがとうございます。

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

2011/02/14 15:52:56
id:ootatmt No.2

ootatmt回答回数1307ベストアンサー獲得回数652011/02/08 19:50:56

ポイント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
id:garyo

ありがとうございます。

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

2011/02/14 15:58:59
id:imo758 No.3

imo758回答回数121ベストアンサー獲得回数192011/02/08 23:14:06

ポイント20pt

http://codepad.org/dv7SypOd

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

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

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

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

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

id:garyo

ありがとうございます。

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

2011/02/14 16:20:26
id:grankoyama No.4

グラ娘。回答回数560ベストアンサー獲得回数1702011/02/09 22:27:55

ポイント20pt

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

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

id:garyo

ありがとうございます。

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

2011/02/14 16:22:52
id:rsc96074 No.5

rsc回答回数4399ベストアンサー獲得回数4032011/02/13 12:29:58

ポイント20pt

 割り算の形から、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);
}
id:garyo

ありがとうございます。

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

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

2011/02/14 16:28:37
  • id:ootatmt
    ちょっと修正して実行時間が0.8sになりました。
  • id:SALINGER
    私の回答は単純に総当りなので実行時間は遅いです。
    実行速度よりも凡庸的なプログラムに落とすことに興味があったので。
    例えば解のループを10000~99999で回しています。
    千の位が7なので明らかに97999より上は無いのにループを回す意味はありませんが、
    7ではないケースにも解を出せるコードであるためには99999でなくてはならない。
     
    実行速度を考慮したプログラムを考えた場合この「明らか」という部分が問題になります。
    真に明らかなのは答えだけなので、ただ答えを出力するプログラムが最速でしょう。
    ただそれでは面白く無いので問題文で明らかな要素は即ち計算式中の桁数と7だけであり、
    それ以外の要素はプログラムで算出するべきと決めておかなければ、
    公平な実行速度比較はできないのではないかと思います。
     
    例えば、リンク先にある「C=0である」これは明らかなので、
    最初からC=0と決めればループは10分の1となります。
    しかしながらこの明らかと判断したのはプログラムではなく人間です。
    そのままC=0を使うことには疑問が残るのです。
     
    回答において回答者がどこまでを明らかな要素と解釈して回答しているかは
    オープン前なのでわかりませんが、解釈が違えば速度比較はできないではないかと思うわけです。
  • id:garyo
    明日で質問終了なので、そろそろ開いてみようと思います。
    実行時間(とマシンスペック)を聞いてみたのは、この問題の場合
    総組み合わせはかなりの数になると思いますが、最近のPCだとそれでも力業で解けてしまうのか、それとも色々アルゴリズムを考えないと解けないのか知りたかったからです。
  • id:imo758
    SALINGERさんのコメント通り
    前提条件がいろいろ不明です

    私のアルゴリズムですが
    とある一桁について判定をまるまる省いているので
    90万通りだけ試している計算になります

    一応c言語移植版を掲載しておきます
    http://codepad.org/sHPUHfKk
    だいたい3倍程度に速くなるようです
  • id:rsc96074
     c=0使ってました。おまけに、割る数の百の位は、1になることも使ってました。(^_^;
    それぞれ、使わないと10倍ずつ遅くなるようです。
     出力などをちょっと改良してみました。
    http://d.hatena.ne.jp/rsc96074/20110214/1297633051
  • id:SALINGER
    角が立たないように回答オープン前にコメントしましたが、
    なんか結果的にrsc96074さんを口撃したみたいな感じになっちゃって申し訳ない。
  • id:rsc96074
     いえいえ、気にしないで下さい。
     それから、実行時間の測定は、ネットで調べたら、clock()関数が使えるようなのでブログで書き直しておきました。(^_^;
  • id:imo758
    卑怯なチューニングを施してみました

    http://codepad.org/gUQ9viQ9

    bのループが 44 回、 同 y が 356 回、 同 z が 387 回、 同 x が 9 回になります
    参考:http://codepad.org/2Gqzo6JM

    codepadに負荷をかけすぎるのはいけないので
    上記自分のPC上にてテストしました

    c言語にて結果出力をさぼると全体で100万回繰り返して53秒
    つまり1回答えを求めるのに平均して53μsecで済んでいます

    時間計測まわりでrscさんのコードを参考にしています
    ありがとうございます

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません