题目43：找出所有具有异常子串整除性的pandigital数之和
本帖最后由 永恒的蓝色梦想 于 2020-6-3 19:27 编辑Sub-string divisibility
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Letbe thedigit,be thedigit, and so on. In this way, we note the following:
Find the sum of all 0 to 9 pandigital numbers with this property.
题目：
1406357289 是一个 pandigital 数，因为它包含了 0 到 9 之间每个数字且只包含了一次。此外它还有一个有趣的子串整除性质。
令表示其第一位数字，表示第二位，以此类推。这样我们可以得到：
求所有具有如上性质的 0 到 9 pandigital 数的和。
跑了10几分钟
3个数。。。
1406357289
1430952867
1460357289
还没跑完，等下补充
#include <iostream>
#include <algorithm>
#include <string>
#include <strstream>
using namespacestd;
void unsigned_to_hex(unsigned int value, std::string& hex_string)
{
std::strstream buffer;
buffer.setf(std::ios::showbase);
buffer<< value;
buffer >> hex_string;
}
//这个数是不是pandight数字
bool isnumpandig(unsigned int n)
{
string str;
unsigned_to_hex(n,str);
sort(str.begin(),str.end());
int i = str.size();
for (int n=0;n<i-1;n++)
{
if(str==str)
return false;
}
return true;
}
//获取一个int类型的位数
int get(unsigned int n)
{
if(n==0) return 1;
int m = 0;
while (n)
{
n/=10;
m++;
}
return m;
}
//获取一个数的第几位
//从左边开始第几个
unsigned intgetnum(unsigned int n,int m)
{
int k = get(n)-m+1; //就是右边的k个
int z = 1;
while (n)
{
if(z==k)
return n%10;
n/=10;
z++;
}
}
int cal(unsigned int num,int a,int b,int c)
{
string str;
unsigned_to_hex(num,str);
int len =str.size();
return (getnum(num,a)*100)+(getnum(num,b)*10)+(getnum(num,c));
}
int main(void)
{
//从0123456789开始
//std::cout<<cal(2802399493,2,3,4);
//2802399493
for (unsigned int n=1023456789;n<=9876543210;n+=1)
{
//满足几个性质
if(isnumpandig(n))
{
//好尴尬
if(cal(n,2,3,4)%2==0)
if(cal(n,3,4,5)%3==0)
if(cal(n,4,5,6)%5==0)
if(cal(n,5,6,7)%7==0)
if(cal(n,6,7,8)%11==0)
if(cal(n,7,8,9)%13==0)
if(cal(n,8,9,10)%17==0)
std::cout<<n<<endl;
}
}
return 0;
} 1406357289
1430952867
1460357289
4106357289
4130952867
4160357289 迷雾少年 发表于 2016-8-30 18:01
跑了10几分钟
3个数。。。
1406357289
能答出欧拉计划这些题的人不多呀` 支持迷雾大神~ 拈花小仙 发表于 2016-8-30 21:21
能答出欧拉计划这些题的人不多呀` 支持迷雾大神~
觉得无聊，就试着做做了{:5_109:} 迷雾少年 发表于 2016-8-30 21:34
觉得无聊，就试着做做了
{:7_113:}迷雾大神在无聊次，我们就又多一份参考文献啦~
你编程技术高，能不能写篇日常关于编程过程中的小技巧整理、和心得体会呢。 拈花小仙 发表于 2016-8-30 21:44
迷雾大神在无聊次，我们就又多一份参考文献啦~
你编程技术高，能不能写篇日常关于编程过程中 ...
会的，谢谢小仙支持 迷雾少年 发表于 2016-8-30 19:04
1406357289
1430952867
1460357289
答案应该是对的，但是我换了一种算法，不要穷举所有数，不然效率太低。
我是生成pandigital，然后依次判断，27.3秒搞定。
['4130952867', '1430952867', '4160357289', '4106357289', '1460357289', '1406357289']
def getPan(n):
if n == 2:
return ['210','120','102','201','021','012']
if n>2:
pan = getPan(n-1)
length = len(pan)
pannew = []
for each in pan:
pannew.append(str(n)+str(each))
pannew.append(str(each)+str(n))
for j in range(1,length):
pannew.append(str(each)[:j]+str(n)+str(each))
return pannew
def judge(plist):
prime =
returnlist = []
for each in plist:
if each == '0':
pass
else:
flag = 1
for j in range(1,8):
if each == '0':
if int(each) % prime != 0:
flag = 0
break
else:
if int(each) % prime != 0:
flag = 0
break
if flag == 1:
returnlist.append(each)
return returnlist
plist = getPan(9)
plist = judge(plist)
print (plist) from itertools import permutations as per
x = lambda l: (l*100+l*10+l) % 2 == 0 and (l*100+l*10+l) % 3 == 0 and (l*100+l*10+l) % 5 == 0 and (l*100+l*10+l) % 7 == 0 and (l*100+l*10+l) % 11 == 0 and (l*100+l*10+l) % 13 == 0 and (l*100+l*10+l) % 17 == 0
for i in per():
if i == 0:
continue
if x(i):
print(i)
(1, 4, 0, 6, 3, 5, 7, 2, 8, 9)
(1, 4, 3, 0, 9, 5, 2, 8, 6, 7)
(1, 4, 6, 0, 3, 5, 7, 2, 8, 9)
(4, 1, 0, 6, 3, 5, 7, 2, 8, 9)
(4, 1, 3, 0, 9, 5, 2, 8, 6, 7)
(4, 1, 6, 0, 3, 5, 7, 2, 8, 9)
请按任意键继续. . . 本帖最后由 芒果加黄桃 于 2017-1-15 22:53 编辑
# encoding:utf-8
# 查找三角形单词个数
from time import time
from itertools import permutations
def euler043():
l_temp = , 10)]
l_primes =
l_pans = []
l_result = []
for each in l_temp:
if each == 0:
continue
if each % 2 != 0:
continue
if each not in (0, 5):
continue
s = ''
for i in list(each):
s += str(i)
l_pans.append(s)
for each in l_pans:
flag = True
for j in range(0, 7):
if not int(each) % l_primes == 0:
flag = False
break
if flag:
l_result.append(int(each))
print(l_result)
if __name__ == '__main__':
start = time()
euler043()
print('cost %.6f sec' % (time() - start))
cost 3.463459 sec 此代码使用matlab编程
Problem43所用时间为491.9989秒
Problem43的答案为16695334890
算是优化到尽头了，还是跑了8分钟。。matlab的确有劣势
%% Problem43.m
%最后编辑时间：2017-06-12 23:13 版本1.0
%找出满足0—9的pandigital数的个数
% Problem43所用时间为491.9989秒
% Problem43的答案为16695334890
function Output = Problem43()
tic
Output = 0;
All = perms('0123456789');
= size(All);
Prime= ;
for ii = 1:M
Num = All(ii,:);
disp(Num)
Cut = zeros(1,7);
Judge = 1;
for jj = 1:7
Cut(jj) = str2double(Num(jj+1:jj+3));
if mod(Cut(jj),Prime(jj)) ~= 0
Judge = 0;
break
end
end
if Judge == 1
Output = Output + str2double(Num);
end
end
toc
disp('此代码使用matlab编程')
disp(['Problem43所用时间为',num2str(toc),'秒'])
disp(['Problem43的答案为',num2str(Output)])
end
渡风 发表于 2017-6-13 00:14
此代码使用matlab编程
Problem43所用时间为491.9989秒
Problem43的答案为16695334890
肯定还可以优化的，我用matlab写的代码，耗时是30多秒 本帖最后由 cq_xuke 于 2017-8-17 18:50 编辑
import time
s=time.clock()
from itertools import permutations
from functools import reduce
primes=
count=0
for pandigits in permutations():
if pandigits==0:
break
i=1
for p in primes:
pan=reduce(lambda x,y:x*10+y,pandigits)
i+=1
if pan % p != 0:
break
else:
count+=reduce(lambda x,y:x*10+y,pandigits)
print(count)
print('Runing time: {0}s'.format(round(time.clock()-s,3)))
16695334890
Runing time: 5.251s from time import time
from itertools import permutations
start = time()
def Euler43(i):
list_1 = ['0','1','2','3','4','5','6','7','8','9']
list_2 = []
str_1 = ''
for each in i:
if each in list_1:
list_1.remove(each)
for each in range(0,len(list_1)):
s = list_1+"".join(i)
list_2.append(s)
returnlist_2
sum = 0
s = permutations('1234567890',3)
for i in s :
if int(''.join(i[:])) % 17==0:
for each in Euler43(i):
if int(each) %13 ==0:
for b in Euler43(each+''.join(i)):
if int(b)%11==0:
for c in Euler43(b+each+"".join(i)):
if int(c)%7==0:
for d in Euler43(c+b+each+"".join(i)):
if int(d)%5 ==0:
for e in Euler43(d+c+b+each+"".join(i)):
if int(e)%3 == 0:
for f in Euler43(e+d+c+b+each+"".join(i)):
if int(f)%2 ==0:
for g in Euler43(f+e+d+c+b+each+"".join(i)):
sum = sum+int(g+f+e+d+c+b+each+"".join(i))
print(sum)
print("Time taken %.6f s" % (time() - start))
16695334890
Time taken 0.002000 s 用的matlab
结果是：
1 6 6 9 5 3 3 4 8 9 0
时间已过 0.127576 秒。
>> '''
ps:利用生成0~9pandigital 和 生成器相结合可以有效缩减时间
answer:
1406357289
1430952867
1460357289
4106357289
4130952867
4160357289
'''
def produce_9_pandigital():
list2=[]
for d0 in range(1,10):
for d1 in range(10):
if d1 != d0:
for d2 in range(10):
if d2 not in :
for d3 in range(10):
if d3 not in :
for d4 in range(10):
if d4 not in :
for d5 in range(10):
if d5 not in :
for d6 in range(10):
if d6 not in :
for d7 in range(10):
if d7 not in :
for d8 in range(10):
if d8 not in :
for d9 in range(10):
if d9 not in :
str_num=str(d0)+str(d1)+str(d2)+str(d3)+str(d4)+str(d5)+str(d6)+str(d7)+str(d8)+str(d9)
yield int(str_num)
for each in produce_9_pandigital():
str_i=str(each)
d_1=1
d_2=2
d_3=3
list1=
for x in range(7):
sum_d1d2d3=int(str_i)*100 + int(str_i)*10 + int(str_i)
if sum_d1d2d3 % list1 != 0:
break
d_1+=1
d_2+=1
d_3+=1
else:
print(each)
def perm(n):
import itertools
for i in range(n):
if i == 1:
listTemp =
else:
listTemp = []
for j in range(i+1):
listTemp.append(j)
list1 = list(itertools.permutations(listTemp, len(listTemp)))
numList = []
for i in range(len(list1)):
numStr = ""
for j in range(len(list1)):
numStr += str(list1)
num = int(numStr)
numList.append(num)
return numList
TempNumList = perm(10)
allNumList = []
for each in TempNumList:
if len(str(each)) == 10:
allNumList.append(each)
def SubNumList(Num):
SubNumList = []
for i in range(1, 8):
SubNumStr = ""
for j in range(3):
SubNumStr += str(Num)
SubNumList.append(int(SubNumStr))
return SubNumList
divisorList =
finalNumList = []
for each1 in allNumList:
TempList = SubNumList(each1)
for i in range(len(TempList)):
if TempList % divisorList != 0:
break
else:
finalNumList.append(each1)
print(finalNumList)
结果是：['1406357289', '1430952867', '1460357289', '4106357289', '4130952867', '4160357289']
用时：4.6644299 秒
import itertools
import time
def get_result():
result = []
for each in itertools.permutations():
target_list =
mark = 1
for i in range(7):
if int(each + each + each) % target_list:
mark = 0
break
if mark:
result.append("".join(each))
return result
print("结果是：{}\n用时：{} 秒".format(get_result(), time.process_time())) 16695334890
Process returned 0 (0x0) execution time : 0.241 s
Press any key to continue.
进行了一通优化……从0.33提到0.24
枚举全排列
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int p[] = {0,2,3,5,7,11,13,17};//0占位
int a[] = {1,0,2,3,4,5,6,7,8,9};
ll parse(int l,int r){
ll res = 0;
for (;l < r;l++){
res *= 10;
res += a;
}
return res;
}
int main(){
ll ans = 0;
do{
bool flag = true;
if (a & 1) continue;
if ( (a+a+a) % 3) continue;
if (a && a != 5)continue;
if (a + a != a && a + a != a + 11)continue;
for (int i = 1;i <= 7;i++){
int t = parse(i,i+3);
if (t % p) {flag = false; break;}
}
if (flag) ans += parse(0,10);
}while(next_permutation(a,a+10));
cout << ans << endl;
return 0;
}
from time import time
def getPan(n):#从大神处copy
if n == 2:
return ['210','120','102','201','021','012']
if n>2:
pan = getPan(n-1)
length = len(pan)
pannew = []
for each in pan:
pannew.append(str(n)+str(each))
pannew.append(str(each)+str(n))
for j in range(1,length):
pannew.append(str(each)[:j]+str(n)+str(each))
return pannew
t = time()
list1 = getPan(9)
list2 = []
for i in list1:
if int(i)%2==0:
if int(i)%3==0:
if int(i)%5==0:
if int(i)%7==0:
if int(i)%11==0:
if int(i)%13==0:
if int(i)%17==0:
list2.append(int(i))
print(list2, '和是：', sum(list2))
print('cos:',time()-t)
页:
[1]
2