（领鱼币）微软的题目，1-9不能重复

迷雾少年

群里发出来的




大家都来积极参与吧，能实现就行，不管什么办法，一起学习

我也写了下（用的递归），代码回复就有了

代码:

游客，如果您要查看本帖隐藏内容请回复

结果(我算出是2个，不知道对没)

游客，如果您要查看本帖隐藏内容请回复

迷雾少年

@liehuo @拈花小仙 @康小泡 @怡静 @零度C 领鱼比啦~

冬雪雪冬

就是只有这两个答案，我不会C，用python试了。

迷雾少年

冬雪雪冬 发表于 2016-8-23 13:50
就是只有这两个答案，我不会C，用python试了。

跑多久出来

冬雪雪冬

迷雾少年 发表于 2016-8-23 13:55
跑多久出来

0.146s

迷雾少年

冬雪雪冬 发表于 2016-8-23 14:00
0.146s

很强势

冬雪雪冬

迷雾少年 发表于 2016-8-23 14:04
很强势

python是解释型语言，速度比C慢很多。不过写程序倒是比C容易且快捷。

迷雾少年

冬雪雪冬 发表于 2016-8-23 14:06
python是解释型语言，速度比C慢很多。不过写程序倒是比C容易且快捷。

我这用C跑了5秒，我估计是我算法问题，用递归慢

冬雪雪冬

迷雾少年 发表于 2016-8-23 14:12
我这用C跑了5秒，我估计是我算法问题，用递归慢

是的，递归是很耗时的。

樱花

看看

lx_Zz

0.009s    用了点技巧优化了搜索

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <windows.h>
   
4. 
   
5. int dp[10];
   
6. int stk[10];
   
7. int sp = 1;
   
8. 
   
9. void Print(int num)
   
10. {
    
11.         printf("success\n");
    
12.         printf("%d", num);
    
13.         for (int i = 8; i > 0; i -= 2)
    
14.         {
    
15.                 printf(" %d", stk[i]);
    
16.         }
    
17.         printf("\n");
    
18.         printf(" ");
    
19.         for (int i = 7; i > 0; i -= 2)
    
20.         {
    
21.                 printf(" %d", stk[i]);
    
22.         }
    
23.         printf("\n");
    
24. }
    
25. 
    
26. void dfs(int temp, int step, int num)
    
27. {
    
28.         if (step > 3 && (num - 3) == temp)
    
29.         {
    
30.                 Print(num);
    
31.         }
    
32.         for (int i = 1; i <= 9; i++)
    
33.         {
    
34.                 if (dp[i] == 0 && dp[(i + 3 + temp) % 10] == 0 && (i + 3 + temp) % 10 != 0)
    
35.                 {
    
36.                         dp[i] = 1;
    
37.                         dp[(i + 3 + temp) % 10] = 1;
    
38.                         stk[sp++] = i;
    
39.                         stk[sp++] = (i + 3 + temp) % 10;
    
40.                         int flag = temp;
    
41.                         if (i + 3 + temp > 10) temp = 1;
    
42.                         else temp = 0;
    
43.                         dfs(temp, step + 1, num);
    
44.                         temp = flag;
    
45.                         dp[i] = 0;
    
46.                         dp[(i + 3 + temp) % 10] = 0;
    
47.                         sp--;
    
48.                         sp--;
    
49.                 }
    
50.         }
    
51. }
    
52. 
    
53. int main()
    
54. {
    
55.         //很明显第一个个数的最高位不是3就是4
    
56. 
    
57.         memset(dp, 0, sizeof(dp));
    
58.         int num = 3;
    
59.         dp[num] = 1;
    
60.         dfs(0, 0, num);//先假设首位是3、从低位开始构造
    
61.         dp[num] = 0;
    
62.         num = 4;
    
63.         dp[num] = 1;
    
64.         dfs(0, 0, num);//假设首位是4、从低位开始构造
    
65.         dp[num] = 0;
    
66. 
    
67.         //system("pause");
    
68.         return 0;
    
69. }
    

复制代码

拈花小仙

仙仙是学碴

去瞧瞧

666

紫瞰

学习一下

TimTimTim

学习一下

husuiwen

飞飞123

没看懂是干什么的啊

飞飞123

看了你运行的懂了

胡闹闹

好厉害的样子·~~~~学习

Pythonfreshman

学习一下