题目62：找出最小的立方数，使得它各位的排列中五个是立方数

欧拉计划

Cubic permutations

The cube, 41063625 can be permuted to produce two other cubes: 56623104 and 66430125 . In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

题目：

立方数 41063625 通过排列可以得到两个另外的立方数: 56623104 和 66430125 。 实际上 41063625 是最小的三个（不多不少）排列是立方数的立方数。

找出最小的立方数，其五个（不多不少）排列是立方数。

迷雾少年

怎么只跑了个3个的 。。除了题目给的。。 。。
1003003001
1030301000
1331000000

jerryxjr1220

1. 5027 127035954683
   
2. 7061 352045367981
   
3. 7202 373559126408
   
4. 8288 569310543872
   
5. 8384 589323567104
   
6. 0.298000097275
   
7. 
   
8. import time
   
9. start_1=time.time()
   
10. def changeNum(n):
    
11.     l=[x for x in str(n)]
    
12.     l.sort()
    
13.     return ''.join(l)
    
14. D,l,num1={},[],0
    
15. for i in range(1,10000):
    
16.     if changeNum(i**3) in D:
    
17.         D[changeNum(i**3)]+=1
    
18.     else:
    
19.         D[changeNum(i**3)]=0
    
20. for d in D:
    
21.     if D.get(d)==4:
    
22.         l.append(d)
    
23. num1=min(l)
    
24. for j in range(1,10000):
    
25.     if changeNum(j**3)==num1:
    
26.         print j,j**3
    
27. print time.time()-start_1

复制代码

愤怒的大头菇

1. list1=[]
   
2. for i in range(10,10000):
   
3.     list1.append(i**3)
   
4. for i in range(len(list1)):
   
5.     temp = i+1
   
6.     count=1
   
7.     tmp = list(str(list1[i]))
   
8.     tmp.sort()
   
9.     while temp+1<len(list1):
   
10.         cmp=list(str(list1[temp]))
    
11.         cmp.sort()
    
12.         if tmp == cmp:
    
13.             count += 1
    
14.         temp += 1
    
15.     if count == 5:
    
16.         print(list1[i])
    
17.         break

复制代码

结果：127035954683。差不多一分钟出结果，慢的不行

芒果加黄桃

1. # encoding:utf-8
   
2. # 找出最小的排列是五个立方数的数
   
3. from time import time
   
4. def euler062(N=1000):
   
5.     l_nums = []
   
6.     l_result = []
   
7.     n = 345
   
8.     while True:
   
9.         l_tmp = sorted([x for x in str(n ** 3)])
   
10.         l_result.append(l_tmp)
    
11.         l_nums.append(n)
    
12.         if l_result.count(l_tmp) == 5:
    
13.             for k in range(1, 6):
    
14.                  print(l_nums[l_result.index(l_tmp)])
    
15.                  l_nums.pop(l_result.index(l_tmp))
    
16.                  l_result.pop(l_result.index(l_tmp))  
    
17.             break
    
18.         n += 1
    
19. if __name__ == '__main__':
    
20.     start = time()
    
21.     euler062()
    
22.     print('cost %.6f sec' % (time() - start))
    

复制代码

5027
7061
7202
8288
8384
cost 0.939648 sec

飘飞的白杨

1. from time import time
   
2. ttt = time()
   
3. def program62_1():
   
4.     n, s = 345, {}
   
5.     while True:
   
6.         temp = tuple(sorted(str(n**3)))
   
7.         if temp not in list(s.keys()):
   
8.             s[temp] = [n]
   
9.         elif len(s[temp]) == 4:
   
10.             print(s[temp]+[n])
    
11.             break
    
12.         else:
    
13.             s[temp] += [n]
    
14.         n += 1
    
15. def program62_2():
    
16.     n, s = 345, []
    
17.     while True:
    
18.         temp = sorted(str(n**3))
    
19.         s += [temp]
    
20.         if s.count(temp) == 5:
    
21.             print([i+345 for i in range(len(s)) if s[i] == temp])
    
22.             break
    
23.         n += 1
    
24. # program62_1()
    
25. program62_2()
    
26. print(time()-ttt)
    

复制代码

najin

用的matlab
结果是：
127035954683
352045367981
373559126408
569310543872
589323567104
时间已过 4.986045 秒。
>>

jerryxjr1220

aardio编写：

1. import win.ui;
   
2. /*DSG{{*/
   
3. mainForm = win.form(text="aardio form";right=686;bottom=314;border="dialog frame";max=false)
   
4. mainForm.add(
   
5. button={cls="button";text="Calculate";left=91;top=207;right=599;bottom=268;z=2};
   
6. edit={cls="edit";left=88;top=67;right=602;bottom=193;edge=1;multiline=1;z=1};
   
7. static={cls="static";text="Euler 62";left=93;top=36;right=236;bottom=61;font=LOGFONT(h=-20);transparent=1;z=3}
   
8. )
   
9. /*}}*/
   
10. 
    
11. mainForm.button.oncommand = function(id,event){
    
12.         mainForm.button.text = "On Calculating..."
    
13.         stime = time.tick();
    
14.         mainForm.edit.print(win.invoke(
    
15.                 function(mainForm){
    
16.                         var tab = {};
    
17.                         for i=1;10000 {
    
18.                                 i3 = tostring(i**3);
    
19.                                 var t = {};
    
20.                                 for j=1;string.len(i3) {
    
21.                                         table.push(t,string.sub(i3,j,j));
    
22.                                 }
    
23.                                 table.sort(t);
    
24.                                 var n = string.join(t,"");
    
25.                                 var flag = true;
    
26.                                 for k,v in tab {
    
27.                                         if k == n {
    
28.                                                 table.push(v,i);
    
29.                                                 flag = false;
    
30.                                                 break;
    
31.                                         }
    
32.                                 }
    
33.                                 if flag {
    
34.                                         tab[n] = {i};
    
35.                                 } else {
    
36.                                         if table.len(tab[n])==5 {
    
37.                                                 return tab[n];
    
38.                                         }
    
39.                                 }
    
40.                         }
    
41.                 },mainForm
    
42.         ))
    
43.         mainForm.edit.print(time.tick()-stime,"ms");
    
44.         mainForm.button.text = "Calculate"
    
45. }
    
46. 
    
47. mainForm.enableDpiScaling();
    
48. mainForm.show();
    
49. 
    
50. return win.loopMessage();

复制代码

[
    5027,
    7061,
    7202,
    8288,
    8384
]
1906        ms

hk1057

import time


def time_it():
        start=time.time()
        fun()
        end=time.time()
        print('cost %.6f Secs'%(end-start))


def sort_num(num):
        list_num=[x for x in str(num)]
        list_num.sort()
        return ''.join(list_num)


def fun():
        num=1
        list_num=[['1']]#[['1234',11,22,33]]6591002036752   6591002036833
        content=0
        index=0
        while True:
                if content:
                        break
                sorted_num=sort_num(num ** 3)
                for each in list_num:
                        if sorted_num in each[0]:
                                each.append(num)
                                if len(each) == 6:#五个排列是立方数
                                        content=1
                                        index=list_num.index(each)
                                break
                else:
                        list_num.append([sorted_num,num])
                num+=1
        print_list=list_num[index]
        print_list=print_list[1:]
        for each in print_list:
                print(each,each**3,sort_num(each**3))
       
               
if __name__=='__main__':
        time_it()
'''
5027 127035954683 012334556789
7061 352045367981 012334556789
7202 373559126408 012334556789
8288 569310543872 012334556789
8384 589323567104 012334556789
cost 1.165871 Secs
'''

哧哧炽

najin 发表于 2017-10-2 20:05
用的matlab
结果是：
127035954683

想知道用MATLAB的代码，如果可以的话可以透露一下吗？非常感谢！

哧哧炽

想知道有没有用MATLAB编码的啊？

王小召

自己代码太垃圾, 转不过来了！只知道题目要求只有五个，所以都要遍历一遍吧。。但是看楼上代码，貌似碰到5直接中断答案也是一样的不变；

结果是：[(5027, 127035954683), (7061, 352045367981), (7202, 373559126408), (8288, 569310543872), (8384, 589323567104)]
用时：22.0429413 秒

1. import time
   
2. 
   
3. 
   
4. def Func1():
   
5.     bool_range = [0] * 100000
   
6.     for i, j in enumerate(bool_range):
   
7.         if not j:
   
8.             start_range = i ** 3
   
9.             length = len(str(start_range))
   
10.             start = i + 1
    
11.             result = [(i, i ** 3)]
    
12.             while len(str(start ** 3)) == length:
    
13.                 if sorted(list(str(start_range))) == sorted(list(str(start ** 3))):
    
14.                     result.append((start, start**3))
    
15.                     bool_range[start] = 1
    
16.                 start += 1
    
17.             if len(result) == 5:
    
18.                 return result
    
19. 
    
20. 
    
21. print("结果是：{}\n用时：{} 秒".format(Func1(), time.process_time()))
    

复制代码

永恒的蓝色梦想

C++ 3ms

1. #include<iostream>
   
2. #include<limits>
   
3. #include<unordered_map>
   
4. 
   
5. 
   
6. 
   
7. size_t hash_permutation(unsigned long long n) {
   
8.     constexpr unsigned long long add[] = { 1ull, 1ull << 5, 1ull << 10, 1ull << 15, 1ull << 20, 1ull << 25, 1ull << 30, 1ull << 35, 1ull << 40, 1ull << 45 };
   
9.     constexpr unsigned short ENLARGE = (unsigned long long)(-1) / (0b10100ull << (9 * 5));
   
10. 
    
11.     unsigned long long t, result = 0;
    
12. 
    
13. 
    
14.     while (n) {
    
15.         t = n;
    
16.         n /= 10;
    
17.         result += add[t - n * 10];
    
18.     }
    
19. 
    
20. 
    
21.     return result * ENLARGE;
    
22. }
    
23. 
    
24. 
    
25. 
    
26. struct MapVal {
    
27.     unsigned long long min;
    
28.     unsigned char count = 0;
    
29. };
    
30. 
    
31. 
    
32. 
    
33. int main() {
    
34.     using namespace std;
    
35.     ios::sync_with_stdio(false);
    
36. 
    
37.     unordered_map<size_t, MapVal> counter;
    
38.     unsigned long long n, cube_of_n;
    
39.     MapVal* ptr;
    
40. 
    
41. 
    
42.     for (n = 1; n < 10000; n++) {
    
43.         cube_of_n = n * n * n;
    
44.         ptr = &counter[hash_permutation(cube_of_n)];
    
45. 
    
46.         if (!(ptr->count)) {
    
47.             ptr->min = cube_of_n;
    
48.         }
    
49. 
    
50.         ptr->count++;
    
51.     }
    
52. 
    
53. 
    
54.     n = numeric_limits<unsigned long long>::max();
    
55. 
    
56.     for (auto& i : counter) {
    
57.         if (i.second.count == 5) {
    
58.             if (i.second.min < n) {
    
59.                 n = i.second.min;
    
60.             }
    
61.         }
    
62.     }
    
63. 
    
64. 
    
65.     cout << n << endl;
    
66.     return 0;
    
67. }

复制代码

ft215378

jerryxjr1220 发表于 2016-10-9 23:25

能不能麻烦大神解释一下 我看不明白

guosl

1. /*
   
2. 答案：127035954683
   
3. 耗时：0.776675秒（单核）
   
4.       0.10129秒（六核）
   
5. */
   
6. #include <iostream>
   
7. #include <algorithm>
   
8. #include <cstring>
   
9. #include <cstdio>
   
10. #include <omp.h>
    
11. using namespace std;
    
12. 
    
13. const int nSteps = 10;
    
14. 
    
15. int main(void)
    
16. {
    
17.   double t = omp_get_wtime();
    
18.   int k = 406;
    
19.   int nR = 0x7fffffff;
    
20.   bool bContinue = true;
    
21. #pragma omp parallel shared(k,bContinue) reduction(min:nR)
    
22.   while (bContinue)
    
23.   {
    
24.     int k2 = 0;
    
25. #pragma omp critical
    
26.     {
    
27.       k2 = k;
    
28.       k += nSteps;
    
29.     }
    
30.     for (int k1 = k2; bContinue && k1 < k2 + nSteps; ++k1)
    
31.     {
    
32.       long long lk = k1;
    
33.       lk = lk * lk * lk;
    
34.       char str[20];
    
35.       sprintf_s(str, "%lld", lk);
    
36.       int nL = strnlen_s(str, 20);
    
37.       sort(str, str + nL);
    
38.       int nCount = 1;
    
39.       int j = k1 + 1;
    
40.       while (bContinue)
    
41.       {
    
42.         long long lj = j;
    
43.         lj = lj * lj * lj;
    
44.         char strj[20];
    
45.         sprintf_s(strj, "%lld", lj);
    
46.         int nLj = strnlen_s(strj, 20);
    
47.         if (nLj > nL)
    
48.           break;
    
49.         sort(strj, strj + nLj);
    
50.         if (strcmp(str, strj) == 0)
    
51.           ++nCount;
    
52.         ++j;
    
53.       }
    
54.       if (nCount == 5)
    
55.       {
    
56.         nR = min(k1, nR);
    
57.         bContinue = false;
    
58. #pragma omp flush(bContinue)
    
59.         break;
    
60.       }
    
61.     }
    
62.   }
    
63.   t = omp_get_wtime() - t;
    
64.   cout << (long long)nR * nR * nR << endl << t << endl;
    
65.   return 0;
    
66. }

复制代码

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. 
   
5. 
   
6. class P62:
   
7. 
   
8.     def __init__(self, test_range):
   
9.         self.test_range = test_range
   
10.         self.cubic_pool = [i ** 3 for i in range(200, test_range)]
    
11.         self.bool_num = [True] * (test_range - 345)
    
12.         self.count = 1
    
13.         self.num_list = []
    
14.         self.find_nums()
    
15. 
    
16.     @staticmethod
    
17.     def is_permutable(num_1, num_2):
    
18.         str_num_1, str_num_2 = str(num_1), str(num_2)
    
19.         if len(str_num_1) != len(str_num_2):
    
20.             return False
    
21.         for each_digit in str_num_1:
    
22.             if each_digit not in str_num_2:
    
23.                 return False
    
24.             else:
    
25.                 str_num_2 = str_num_2.replace(each_digit, '', 1)
    
26.         return True
    
27. 
    
28.     def check_num(self, num_1):
    
29.         test_num = num_1 + 1
    
30.         while test_num < self.test_range:
    
31.             if self.bool_num[test_num - 345] and \
    
32.                     self.is_permutable(self.cubic_pool[num_1 - 200], self.cubic_pool[test_num - 200]):
    
33.                 self.count += 1
    
34.                 self.num_list.append(test_num)
    
35.                 self.bool_num[test_num - 345] = False
    
36.             test_num += 1
    
37. 
    
38.     def find_nums(self):
    
39.         for num0 in range(345, self.test_range):
    
40.             if self.bool_num[num0 - 345]:
    
41.                 self.num_list = [num0]
    
42.                 self.count = 1
    
43.                 self.check_num(num0)
    
44.                 if self.count == 5:
    
45.                     print(self.num_list)
    
46.                     print([self.cubic_pool[j - 200] for j in self.num_list])
    
47.                     break
    
48. 
    
49. 
    
50. res = P62(10000)
    
51. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

[5027, 7061, 7202, 8288, 8384]
[127035954683, 352045367981, 373559126408, 569310543872, 589323567104]
It costs 23.116533 s