题目32：找出所有能写成 pandigital 数字乘积的数字之和
Pandigital productsWe shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
题目：
如果一个 n 位数使用了 1 到 n 中每个数字且只使用了一次，我们称其为 pandigital。例如，15234 这个五位数，是 1 到 5 pandigital 的。
7254 是一个不寻常的数，因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了一个1到 9 的 pandigital 组合。
找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。
提示: 有的乘积数字能够被多个乘法算式得到，所以在计算时要记得只计算它们一次。 额 4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
bool mycalc(int a,int b,int c)
{
string myResult;
char buf;
itoa(a,buf,10);
myResult+=buf;
itoa(b,buf,10);
myResult+=buf;
itoa(c,buf,10);
myResult+=buf;
sort(myResult.begin(),myResult.end());
return myResult==string("123456789");
}
int main()
{
for (int n=2;n<=100000;n++)
{
for (int m=2;m<=100000;m++)
{
int mul = n*m;
if(mycalc(m,n,mul))
{
std::cout<<n<<"*"<<m<<"="<<mul<<endl;
}
}
}
return 0;
} list1 =
list2 = []
for i in range(1,100):
for j in range(100,10000):
temp = True
if len(str(i))+len(str(j))+len(str(i*j)) == 9:
for each in list1:
if str(each) not in (str(i)+str(j)+str(i*j)):
temp = False
break
if temp:
if i*j not in list2:
list2.append(i*j)
print(sum(list2))
结果:45228 本帖最后由 jerryxjr1220 于 2016-10-12 12:41 编辑
楼上答案正确：45228
def pan(n): return len(n)==9 and "123456789".strip(n)==""
prod = set()
for i in range(1,10):
for j in range(1234,9877):
if pan(str(i)+str(j)+str(i*j)): prod.add(i*j)
for i in range(12,99):
for j in range(123,988):
if pan(str(i)+str(j)+str(i*j)): prod.add(i*j)
print (sum(prod)) # encoding:utf-8
# pandigital 之和
from time import time
def isDup(N):
if str(N).find('0') > -1 :
return False
if len(str(N)) == len(set(str(N))):
return True
return False
def isPanDigital(n1, n2, n3):
l_t = []
l_t.extend(list(str(n1)))
l_t.extend(list(str(n2)))
l_t.extend(list(str(n3)))
l_t = set(l_t)
if len(l_t) == 9:
return True
return False
def euler032():
l_result = []
for i in range(1, 10):
for j in range(1234, 9877):
if isDup(j):
k = i * j
if k > 9876:
break
if isDup(k):
if isPanDigital(i, j, k):
#print(i, j, k)
l_result.append(k)
for i in range(12, 99):
for j in range(123, 988):
if isDup(j):
k = i * j
if k > 9876:
break
if isDup(k):
if isPanDigital(i, j, k):
#print(i, j, k)
l_result.append(k)
print(sum(set(l_result)))
if __name__ == '__main__':
start = time()
# print(isDup(121))
euler032()
print('cost %.6f sec' % (time() - start))
45228
cost 0.078008 sec
时间已过 30.829161 秒。
此代码使用matlab编程
Problem32所用时间为30.8314秒
Problem32的答案为45228
%% Problem32
%找出所有能写成pandigital 数字的乘积之和
function Output = Problem32()
tic
value = ;
Judge = value * value';
Record = [];
All = perms();
= size(All);
for aa = 1:M
%tempvector = str2num(num2str(aa)')';
tempvector = All(aa, :);
disp(tempvector)
if tempvector * tempvector' == Judge
t = tempvector;
a = t(1);
b = 1000*t(2) + 100*t(3) +10*t(4) + t(5);
c = 1000*t(6) + 100*t(7) +10*t(8) + t(9);
if a * b == c
Record = union(Record, c);
end
d = t(1)*10 + t(2);
e = 100*t(3) + 10*t(4) +t(5);
f = 1000*t(6) + 100*t(7) + 10*t(8) + t(9);
if d * e == f
Record = union(Record, f);
end
else
continue
end
end
toc
Output = sum(Record);
disp('此代码使用matlab编程')
disp(['Problem32所用时间为',num2str(toc),'秒'])
disp(['Problem32的答案为',num2str(Output)]) #include <stdio.h>
int is_pandigital(int a, int b, int product);
int main()
{
int a, b, product;
int sum = 0;
int results = {0};
int i = 0, j;
int flag = 1;
for(a = 1; a < 1024 / 2; a++)
{
for(b = a; b < 4096; b++)
{
product = a * b;
if(is_pandigital(a, b, product))
{
for(j = 0; j < i; j++)
{
if(results == product)
{
flag = 0;
}
}
if(flag)
{
results = product;
sum += product;
printf("%d * %d = %d\n", a, b, product);
i++;
}
flag = 1;
}
}
}
printf("\n%d\n", sum);
return 0;
}
int is_pandigital(int a, int b, int product)
{
int count = 0;
int flag = {0};
int i;
while(a > 0)
{
flag++;
a /= 10;
count++;
if(count > 9)
{
return 0;
}
}
while(b > 0)
{
flag++;
b = b / 10;
count++;
if(count > 9)
{
return 0;
}
}
while(product > 0)
{
flag++;
product = product / 10;
count++;
if(count > 9)
{
return 0;
}
}
for(i = 1; i < 10; i++)
{
if(flag != 1)
{
return 0;
}
}
return 1;
} 本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:34 编辑
JonTargaryen 发表于 2017-5-23 19:54
def is_pandigital(a, b, product):
flag = * 10
count = 0
while a > 0:
flag += 1
a //= 10
count += 1
if count > 9:
return 0
while b > 0:
flag += 1
b //= 10
count += 1
if count > 9:
return 0
while product > 0:
flag += 1
product //= 10
count += 1
if count > 9:
return 0
for each in flag:
if each != 1:
return 0
return 1
def main():
results = []
answer = 0
for a in range(1, 512):
for b in range(a, 4096):
product = a * b
if is_pandigital(a, b, product):
for each in results:
if each == product:
flag = 0
if flag:
results.append(product)
answer += product
print("%d * %d = %d" %(a, b, product))
flag = 1
print(answer)
return
if __name__ == '__main__':
main() import java.util.Arrays;
public class PandigitalProducts{
public static void main(String[] args){
int[] m = new int;
int[] n = new int;
int[] result = new int;
int[] consequence = new int;
int r = 0,sum = 0;
int count_1 = 0,count_2 = 0,count_3 = 0;
int i = 0;
for(int a = 1;a < 100;a ++){
count_1 = Record(m,a);
if(Repeat(m,count_1)){
continue;
}
for(int b = 101;b < 10000;b ++){
count_2 = Record(n,b);
if( Repeat(n,count_2) ){
continue;
}
if(Pandigital(m,n,count_2) ){
r = a * b;
count_3 = Record(result,r);
if(Repeat(result,count_3) || count_1+count_2+count_3 != 9){
continue;
}
if(Pandigital(result,m,count_1) && Pandigital(result,n,count_2)){
Arrays.sort(consequence);
if(Arrays.binarySearch(consequence,r) < 0){
sum += r;
}
System.out.println(a+"*"+b+"="+r);
consequence = r;
}
}
else{
continue;
}
}
}
System.out.println("去掉重复数字的和为"+sum);
}
public static int Record(int[] record,int x){
int count = 0;
for(int i = 0;i < record.length;i ++){
record = 0;
}
int temp = x;
for(int i = 0;temp != 0;i ++){
record = temp % 10;
count++;
temp /= 10;
}
return count;
}
public static boolean Pandigital(int[] record,int[] judge,int count){
boolean flag = true;
top:for(int i = 0;i < count;i ++){
for(int j = 0;j < record.length;j ++){
if(judge == record){
flag = false;
break top;
}
}
}
return flag;
}
public static boolean Repeat(int[] a,int count){
boolean flag = false;
for(int i = 0;i < count-1;i ++){
for(int j = i+1;j < count;j ++){
if(a == a && !flag){
flag = true;
break;
}
}
}
for(int i = 0;i < count;i ++){
if(a == 0){
flag = true;
}
}
return flag;
}
}
4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
去掉重复数字的和为45228 本帖最后由 王小召 于 2019-6-13 12:08 编辑
6952 = 4 * 1738
7852 = 4 * 1963
5796 = 12 * 483
5346 = 18 * 297
5346 = 27 * 198
4396 = 28 * 157
7254 = 39 * 186
5796 = 42 * 138
7632 = 48 * 159
结果表单：
代数和:45228
用时：0.2964 秒import time
def get_pandigital():
code_list = list(map(str, range(1, 10)))
target = []
# x < y
for x in range(1, 100000):
for y in range(x, 100000):
length = len(str(x) + str(y) + str(x * y))
# eg：100 * 100 = 10000 已经超过9个字母了所以100 * (101,102...)没必要继续了
if length > 9:
break
else:
if length == 9:
l1 =
l1.sort()
if code_list == l1:
print("{} = {} * {}".format(x*y, x, y))
target.append(x*y)
return list(set(target)), sum(list(set(target)))
pg_list, summary = get_pandigital()
print("结果表单：{}\n代数和:{}\n用时：{:.4f} 秒".format(pg_list, summary, time.process_time())) 45228
Process returned 0 (0x0) execution time : 0.020 s
Press any key to continue.
经分析，算式只可能有一位数*四位数=四位数 或 两位数*三位数=四位数 两种形式
暴力枚举后用set判重
#include<iostream>
#include<set>
#include<cstring>
using namespace std;
int stat;
bool parse(int x){
while(x){
int t = x % 10;
if (stat) return false;
stat = 1;
x /= 10;
}
return true;
}
bool pan(int x,int y,int z){
memset(stat,0,sizeof(stat));
if (!parse(x))return false;
if (!parse(y))return false;
if (!parse(z))return false;
if (stat) return false;
return true;
}
int main(){
set<int> s;
int sum = 0;
for (int a = 2;a < 10;a++){
for (int b = 1002;b < 10000;b++){
int c = a * b;
if (c >= 10000) break;
if (pan(a,b,c)) s.insert(c);
}
}
for (int a = 12;a < 100;a++){
for (int b = 102;b < 1000;b++){
int c = a * b;
if (c >= 10000) break;
if (pan(a,b,c)) s.insert(c);
}
}
for (set<int>::iterator it = s.begin();it != s.end();it++){
sum += *it;
}
cout << sum << endl;
return 0;
}
start = time.time()
d = 0
check = []
for a in range(1, 100):
for b in range(1,10000):
c = a*b
check1 = list(str(a)+str(b)+str(c))
check1.sort()
check2 = list(set(check1))
check2.sort()
if '0' not in str(a) and '0' not in str(b) and '0' not in str(c) and check1 == check2 and len(check2) == 9:
print("%d * %d = %d" %(a,b,c))
check.append(c)
check = list(set(check))
for each in check:
d+= each
print("去除重复代数后的代数和为%d" %d)
end = time.time()
print("共用时%f秒" %(end - start))
4 * 1738 = 6952
4 * 1963 = 7852
12 * 483 = 5796
18 * 297 = 5346
27 * 198 = 5346
28 * 157 = 4396
39 * 186 = 7254
42 * 138 = 5796
48 * 159 = 7632
去除重复代数后的代数和为45228
共用时2.755275秒
#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 == 1)
{
return 0;
}
a = 1;
j /= 10;
}
return 1;
}
main()
{
int i, j, k, sum = 0, e, x = 0, y;
char str;
int a = { 0 }; //用于标记数字是否已经加过
printf("k = ");
for (i = 1; i < 99; i++)
{
for (j = 100; j < 9999; j++)
{
k = i * j;
if (k > 10000)
{
break;
}
if ((check_num(k) == 0) || (check_num(j) == 0) || (check_num(i) == 0))
{
continue;
}
y = k;
while (y)
{
e = y % 10;
str = e + '0';
y /= 10;
}
y = j;
while (y)
{
e = y % 10;
str = e + '0';
y /= 10;
}
y = i;
while (y)
{
e = y % 10;
str = e + '0';
y /= 10;
}
str = '\0';
if (strlen(str) < 9)
{
continue;
}
y = atoi(str);
if (check_num(y))
{
if (a == 0)
{
sum += k;
printf("%d ", k);
}
a = 1;
}
x = 0;
}
}
printf("\nsum = %d\n", sum);
}
答案：
k = 6952 7852 5796 5346 4396 7254 7632
sum = 45228 #找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。
from time import *
'''
如果一个n位数使用了1到n中每个数字且只使用了一次，
我们称其为 pandigital。
例如，15234 这个五位数，是1到5pandigital 的。
7254 是一个不寻常的数，
因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了一个1到9的 pandigital 组合。
找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。
'''
#处理字符串
def deal_str(string):
string_list = []
for each in string:
string_list.append(each)
string_list.sort()
return string_list
start = time()
numlist = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
res = []
c = 1
for a in range(1, 98):
for b in range(123, 9876):
c = a * b
if deal_str(str(a) + str(b) + str(c)) == numlist:
res.append()
#去除重复项
result = []
for each in res:
if each not in result:
result.append(each)
else:
res.remove(each)
#计算
total = 0
for each in res:
total += each
end = time()
print(total)
print("用时%.2f秒" % (end - start))
/*
答案：45228
耗时：0.0250623秒
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int main(void)
{
char str = "123456789";
vector<int> v;
do
{
char str1, str2, str3;
for (int i = 1; i <= 2; ++i)//对第一个乘数的长度进行枚举
{
memset(str1, 0, sizeof(str1));
strncpy(str1, str, i);//得到第一个乘数
int j = 5 - i;//求得第二个乘数的长度
memset(str2, 0, sizeof(str2));
strncpy(str2, str + i, j);//得到第二个乘数
memset(str3, 0, sizeof(str3));
strncpy(str3, str + 5, 4);//得到第三个乘数
int a1 = atoi(str1), a2 = atoi(str2), a3 = atoi(str3);
if (a1 * a2 == a3)
v.push_back(a3);//满足要求保存
}
} while (next_permutation(str, str + 9));//求出下一个组合
//去重
sort(v.begin(), v.end());
auto itr_end = unique(v.begin(), v.end());
//求和
int nSum = 0;
for (auto itr = v.begin(); itr != itr_end; ++itr)
nSum += *itr;
cout << nSum << endl;
return 0;
}
简单想一想，可能的组合只有这两种：
* x **** = ****
** x *** = ****
剩下的就很简单了
另外，为提升速度，可以使用位运算而不是字符串来存储各个位。
代码：
use std::collections::HashSet;
fn bits(x: usize) -> u32 {
let mut x = x;
let mut ans = 0;
while x != 0 && x % 10 != 0 {
ans ^= 1 << (x % 10 - 1);
x /= 10;
}
ans
}
fn main() {
let mut v = HashSet::new();
for i in 1..=9 {
for j in 1..=9999 {
if i * j > 9999 {
break;
}
if bits(i) + bits(j) + bits(i * j) == 0b111111111 {
v.insert(i * j);
println!("{} * {} = {}", i, j, i * j)
}
}
}
for i in 1..=99 {
for j in 1..=999 {
if i * j > 9999 {
break;
}
if bits(i) + bits(j) + bits(i * j) == 0b111111111 {
v.insert(i * j);
println!("{} * {} = {}", i, j, i * j)
}
}
}
println!("{}\n{}", v.len(), v.iter().sum::<usize>());
}
输出：
$ time ./main
4 * 1738 = 6952
4 * 1963 = 7852
12 * 483 = 5796
18 * 297 = 5346
27 * 198 = 5346
28 * 157 = 4396
39 * 186 = 7254
42 * 138 = 5796
48 * 159 = 7632
7
45228
real 0m0.002s
user 0m0.002s
sys 0m0.000s
页:
[1]