题目38：最大的能够通过一个固定数与1,2,3,...相乘得到的1到9pandigital数是多少？
本帖最后由 欧拉计划 于 2015-5-2 11:22 编辑Pandigital multiples
Take the number 192 and multiply it by each of 1, 2, and 3:
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?
题目：
将 192 与 1, 2, 3 分别相乘得到：
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
将这三个乘积连接起来我们得到一个 1 到 9 的 pandigital 数， 192384576。我们称 192384576 是 192 和 (1,2,3) 的连接积。
通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数：918273645，这个数是 9 和 (1,2,3,4,5) 的连接积。
用一个整数与 1,2, ... , n（n 大于 1）的连接积构造而成的 1 到 9 pandigital 数中最大的是多少？
没懂什么意思，，不过感觉不难。。 list1 =
list2 = []
for i in range(1,100000):
str_1 = ''
for each in list1:
str_1 += str(i*each)
if len(str_1)>=9:
break
if len(str_1) == 9:
tmp = True
for each in list1:
if str(each) not in str_1:
tmp = False
break
if tmp:
list2.append(int(str_1))
list2.sort()
print(list2[-1])
932718654 # encoding:utf-8
# 一个整数与1,2,3...N的乘积链接构成1-9的pandigital，寻找最大的数
from time import time
def euler038():
for i in range(1, 9877):
tmp = ''
for t in range(1, 10):
tmp += str(i * t)
if len(tmp) > 9:
break
if len(tmp) == 9:
if not '123456789'.strip(tmp):
print(i, )
break
if __name__ == '__main__':
start = time()
euler038()
print('cost %.6f sec' % (time() - start))
1
9
192
219
273
327
6729
6792
6927
7269
7293
7329
7692
7923
7932
9267
9273
9327
cost 0.020014 sec %% Problem38.m
% 最后编辑时间：17-06-15 0:45
% 通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数:918273645,这个数是918273645,这个数是 9 和 (1,2,3,4,5) 的连接积。
% 用一个整数与 1,2, ... , n(n 大于 1)的连接积构造而成的 1 到 9 pandigital 数中最大的数是多少？
%分析 ：1位数1 * 9*[ 1 2 3 4 5]
% 2位数 * 不可能存在这样的数
% 3位数 * 三位数小于 333
% 4位数 * 四位数大于5000
%% Problem38.m
% 最后编辑时间：17-06-15 0:45
% 通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数:918273645,这个数是918273645,这个数是 9 和 (1,2,3,4,5) 的连接积。
% 用一个整数与 1,2, ... , n(n 大于 1)的连接积构造而成的 1 到 9 pandigital 数中最大的数是多少？
%分析 ：1位数1 * 9*[ 1 2 3 4 5]
% 2位数 * 不可能存在这样的数
% 3位数 * 三位数小于 333
% 4位数 * 四位数大于5000
% Problem38所用时间为： 1.43秒
% Problem358的答案为： 932718654
function Output = Problem38()
tic
Output = 0;
% 一位数
for ii = 1:9
Str = [];
FirstJudge = 0;
for jj = 1:9
Str = ;
if length(Str) == 9
FirstJudge = 1;
break
elseif length(Str) > 9
FirstJudge = 0;
break
end
end
if FirstJudge == 1
if str2double(Str) > Output
if strcmp(sort(Str),'123456789') == 1
Output = str2double(Str);
end
end
end
end
%三位数
for kk = 100:333
Str = ;
if str2double(Str) > Output
if strcmp(sort(Str),'123456789') == 1
Output = str2double(Str);
end
end
end
%四位数
for ll = 5001:9999
Str = ;
if str2double(Str) > Output
if strcmp(sort(Str),'123456789') == 1
Output = str2double(Str);
end
end
end
toc
disp('此代码使用matlab编程')
disp(['Problem38所用时间为： ',num2str(toc),'秒'])
disp(['Problem358的答案为： ',num2str(Output)]) from time import time
start = time()
def isPandingital(n):
i =1
str_1 = ''
tag = True
while i<10:
str_1 = str_1+str(n*i)
i = i + 1
if '0' not in str_1:
iflen(set(str_1))==9 and len(str_1)==9:
return True
break
return False
def getPandingital(n):
i = 1
str_1 = ''
tag = True
while i < 10:
str_1 = str_1+str(n * i)
i = i + 1
if '0' not in str_1:
if len(set(str_1)) == 9 and len(str_1) == 9:
return int(str_1)
num = 10000 #n需要大于1,所以需要两个数组合,num不会超过4位数,为保险,可以取num = 100000
while num > 0:
ifnot isPandingital(num):
num -=1
else:
print(num)
print(getPandingital(num))
break
print("Program running cost %4f secs!" % (time() - start))
9327
932718654
Program running cost 0.005000 secs! 用的matlab
结果是：
932718654
时间已过 2.374731 秒。
>>
def concatenating(num):
sum = 0
numTempList = []
for i in range(1, 10):
sum += len(str(num * i))
numTempList.append(str(num * i))
if sum == 9:
break
elif sum > 9:
break
finalNumStr = ""
for each in numTempList:
finalNumStr += each
finalNum = int(finalNumStr)
return finalNum
def isPandigital(num):
if len(str(num)) != 9:
return False
else:
numTempList = []
refNumList =
for i in range(len(str(num))):
numTempList.append(int(str(num)))
if list(set(numTempList)) == refNumList:
return True
else:
return False
numList = []
for num in range(1, 1000000):
if isPandigital(concatenating(num)):
numList.append(concatenating(num))
numList.sort()
print(numList[-1])
932718654 本帖最后由 王小召 于 2019-6-14 10:24 编辑
最大值是：932718654
用时:0.4212027 秒
import time
def is_pandigital(num):
l =
l.sort()
if l == :
return True
else:
return False
def cal_nums():
results = []
for num in range(1, 100000):
length = 2
tmp = ""
for i in range(1, 10):
tmp += str(num * i)
if len(str(tmp)) < 9:
continue
elif len(str(tmp)) > 9:
break
else:
if is_pandigital(tmp):
results.append((tmp, num, length))
return results
results = cal_nums()
max_result = max(int(each) for each in results)
print("最大值是：{}\n用时:{} 秒".format(max_result, time.process_time())) 932718654
Process returned 0 (0x0) execution time : 0.036 s
Press any key to continue.
既然题目已给出918273645这一解，可直接讨论首位为9的情况
一位数的构造只有上述一种
其余情况只有四位数满足题意
由连接积的定义，逆序枚举效率更高
#include<iostream>
using namespace std;
bool pan(int x,int y){
int digit = {0};
while(x){
digit = 1;
x /= 10;
}
while(y){
digit = 1;
y /= 10;
}
if (digit) return false;
for (int i = 1;i < 10;i++)
if (!digit) return false;
return true;
}
int main(){
for (int i = 9876;i > 9011;i--){
int t = 2*i;
if (pan(i,2*i)) {cout << i << t << endl; break;}
}
return 0;
}
#include <stdio.h>
#include <string.h>
int check_num(int);
int check_num(int num)
{
int i, j, a = { 0 };
j = num;
while (j)
{
i = j % 10;
if (i == 0)
{
return 0;
}
if (a)
{
return 0;
}
j /= 10;
a = 1;
}
return 1;
}
main()
{
char str, rts;
int i, j, k, max = 0;
for (i = 5000; i < 10000; i++)
{
j = i * 2;
sprintf(str, "%d", i);
sprintf(rts, "%d", j);
strcat(str, rts);
k = atoi(str);
if (check_num(k))
{
max = max > i ? max : i;
}
}
printf("%d", max);
}
9327 import time as t
start = t.perf_counter()
def is_pandigital(a_num):
tar =
list_num =
if len(list_num) != 9:
return False
elif tar == list(set(list_num)):
return True
pandigitals = []
for i in range(2, 10):
multiplier = 10 ** (int(9 // i) - 1)
while True:
res = ''
for j in range(1, i + 1):
res += str(multiplier * j)
res = int(res)
if res > 1e9:
break
elif is_pandigital(res):
pandigitals.append(res)
multiplier += 1
print(max(pandigitals))
print("It costs %f s" % (t.perf_counter() - start))
932718654
It costs 0.031873 s $ time ./main
932718654
real 0m0.002s
user 0m0.000s
sys 0m0.002s
fn bits(x: u32) -> u32 {
let mut x = x;
let mut ans = 0;
while x != 0 {
if x%10 == 0 {
return 0;
}
let y = 1 << (x % 10 - 1);
if ans & y != 0 {
return 0;
}
ans |= y;
x /= 10;
}
ans
}
fn is_pandigital(x: u32) -> bool {
let mut tot = 0;
for i in 1..=9 {
let b = bits(i*x);
if b == 0 || tot & b != 0 {
return false;
}
tot |= b;
if tot == 0b111111111 {
return true;
}
}
false
}
fn pandigital(x: u32) -> u32 {
let v = &mut ;
let mut vi = 0;
let mut i = 1;
while vi != 9 {
let mut y = x*i;
while y != 0 {
v = y / 10u32.pow(y.ilog10());
vi += 1;
y %= 10u32.pow(y.ilog10());
}
i += 1;
}
let mut sum = 0;
for i in 0..=8 {
sum += v * 10u32.pow(i as u32);
}
sum
}
#
mod tests {
use super::*;
#
fn test_is_pandigital() {
assert!(is_pandigital(192));
assert!(is_pandigital(9));
assert!(is_pandigital(1));
assert!(!is_pandigital(191));
}
#
fn test_pandigital() {
assert_eq!(pandigital(9),918273645);
assert_eq!(pandigital(192),192384576);
}
}
fn main () {
// 要使 n > 1, 最多是4位数
let v:Vec<u32> = (1..1e5 as u32).filter(|&x| is_pandigital(x)).collect();
let p:Vec<u32> = v.into_iter().map(|x| pandigital(x)).collect();
println!("{}", p.iter().max().unwrap());
}
页:
[1]