手动 Permutation
C++ 3ms#include<iostream>
#include<array>
int main() {
using namespace std;
ios::sync_with_stdio(false);
array<bool, 10>free;
array<unsigned char, 10>d;
free.fill(true);
for (d = 1; d ^ 10; d++) {
free] = false;
for (d = 0; d ^ 10; d++) {
if (free]) {
free] = false;
for (d = 0; d ^ 10; d++) {
if (free]) {
free] = false;
for (d = 0; d ^ 10; d += 2) {
if (free]) {
free] = false;
for (d = 3 - (d + d) % 3; d < 10; d += 3) {
if (free]) {
free] = false;
for (d = 0; d ^ 10; d += 5) {
if (free]) {
free] = false;
for (d = 0; d ^ 10; d++) {
if (free] && !((d * 100 + d * 10 + d) % 7)) {
free] = false;
for (d = 0; d ^ 10; d++) {
if (free] && !((d * 100 + d * 10 + d) % 11)) {
free] = false;
for (d = 0; d ^ 10; d++) {
if (free] && !((d * 100 + d * 10 + d) % 13)) {
free] = false;
for (d = 0; d < 10; d++) {
if (free] && !((d * 100 + d * 10 + d) % 17)) {
for (auto i : d) {
cout.put('0' + i);
}
cout << '\n';
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
}
free] = true;
}
} 渡风 发表于 2017-6-13 00:14
此代码使用matlab编程
Problem43所用时间为491.9989秒
Problem43的答案为16695334890
matlab跟python很像啊 #include <stdio.h>
#include <math.h>
main()
{
long long int i, sum = 0;
int j, k, flag = 1, array = { 2, 3, 5, 7, 11, 13, 17 }, temp = { 0 };
char str, num;
for (int a = 1; a < 10; a++)
{
temp = 1;
str = a + '0';
for (int b = 0; b < 10; b++)
{
if (temp)
{
continue;
}
temp = 1;
str = b + '0';
for (int c = 0; c < 10; c++)
{
if (temp)
{
continue;
}
temp = 1;
str = c + '0';
for (int d = 0; d < 10; d++)
{
if (temp)
{
continue;
}
temp = 1;
str = d + '0';
for (int e = 0; e < 10; e++)
{
if (temp)
{
continue;
}
temp = 1;
str = e + '0';
for (int f = 0; f < 10; f++)
{
if (temp)
{
continue;
}
temp = 1;
str = f + '0';
for (int g = 0; g < 10; g++)
{
if (temp)
{
continue;
}
temp = 1;
str = g + '0';
for (int h = 0; h < 10; h++)
{
if (temp)
{
continue;
}
temp = 1;
str = h + '0';
for (int m = 0; m < 10; m++)
{
if (temp)
{
continue;
}
temp = 1;
str = m + '0';
for (int n = 0; n < 10; n++)
{
if (temp)
{
continue;
}
temp = 1;
str = n + '0';
str = '\0';
for (j = 0; j < 7; j++)
{
num = str;
num = str;
num = str;
num = '\0';
k = atoi(num);
if (k % array)
{
flag = 0;
break;
}
}
if (flag)
{
i = atof(str);
sum += i;
printf("%lld\n", i);
}
flag = 1;
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
temp = 0;
}
printf("\n%lld\n", sum);
}
1406357289
1430952867
1460357289
4106357289
4130952867
4160357289
sum = 16695334890 这个问题我们用OpenMP的平行编程来处理
/*
答案：16695334890
耗时：0.276207秒（单核）
0.0415891（八核）
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <omp.h>
using namespace std;
const int d[] = { 2,3,5,7,11,13,17 };
//线程里面不能处理的内容太少，否则反而把更多的时间花在线程切换和等待上
const int nSteps = 256;//线程每次处理的数的个数
int main(void)
{
char str = "0123456789";
long long nSum = 0;
volatile bool bContinue = true;
#pragma omp parallel shared(bContinue,str) reduction(+:nSum)
while (bContinue)
{
char str1, str2;
int nK = 0;
#pragma omp critical
{
//获得当前要处理的数据
strcpy_s(str1, str);
for (nK = 0; bContinue && nK < nSteps; ++nK)
bContinue = next_permutation(str, str + 10);//处理出给其他线程用的值
}
for (int j = 0; j < nK; ++j)
{
bool bFlag = true;
for (int i = 0; i < 7; ++i)
{
strncpy_s(str2, str1 + (i + 1), 3);
str2 = 0;
int a = atoi(str2);
if (a % d != 0)
{
bFlag = false;
break;
}
}
if (bFlag)
{
long long k = 0;
for (int i = 0; i < 10; ++i)
{
k *= 10;
k += int(str1 - 48);
}
nSum += k;
}
next_permutation(str1, str1 + 10);
}
}
cout << nSum << endl;
return 0;
}
import time as t
from itertools import permutations
start = t.perf_counter()
def have_traits(a_tuple):
list_dn = []
divisors =
for n in range(1, 8):
list_dn.append(int(a_tuple + a_tuple + a_tuple))
for index in range(7):
if not (list_dn // divisors == list_dn / divisors):
return False
else:
return True
num_list = list(permutations('0123456789'))
nums = []
for num_tuple in num_list:
if len(num_tuple) == 10 and have_traits(num_tuple):
num_str = ''
for i in range(10):
num_str += num_tuple
nums.append(int(num_str))
print(nums)
print(sum(nums))
print("It costs %f s" % (t.perf_counter() - start))
16695334890
It costs 10.803681 s
页:
1
[2]