一道竞赛题，想了两天无果，虽然考试结束，我还是希望得到指点

honhon

/*本来想悬赏的，因为一道题的解惑比我的鱼币重要多了，但是提示我是新鱼友不让我发，厚脸皮希望各位帮帮我，
讲讲思路也好，不必写出代码*/
素数划分
Time Limit:1000MS  Memory Limit:65535K
题型: 编程题   语言: 无限制
描述
给定一个最多不超过30个字符的数字字符串（只由0到9，十个数字构成），如果将该字符串切割成
多段（每一段数字不超过6个字符），如果能找到一种划分使每一段构成的数字都是质数，则输出“YES”
，怎么也找不到，输出“NO”。
例如
1447160917891993
可以划分为
1447 1609 17 89 199 3
均为质数，输出YES

再例如
999444
输出NO

输入格式
不超过30个字符的数字串
输出格式
YES或NO
输入样例
1447160917891993
输出样例
YES

conn

还没看懂，晚上看看

honhon

conn 发表于 2016-12-16 11:53
还没看懂，晚上看看

嗯嗯，谢谢

小山童鞋

回溯，从第一个字符开始找一个一个往后挪，如果构成了质数就接着往下一个子串找质数，同样的知道找到最后，如果找完了纯在就输出YES，否则就回溯到上一层再往下找，这整个过程可以用递归来完成的。。

我看看明天把代码贴上来

小山童鞋

其实相当于构造一颗搜索树

honhon

小山童鞋 发表于 2016-12-16 16:47
回溯，从第一个字符开始找一个一个往后挪，如果构成了质数就接着往下一个子串找质数，同样的知道找到最后， ...

今天下午想了一个下午才想到用递归，不过老是失败，没学过数据结构大神好厉害，几下就看出来

honhon

小山童鞋 发表于 2016-12-16 16:47
回溯，从第一个字符开始找一个一个往后挪，如果构成了质数就接着往下一个子串找质数，同样的知道找到最后， ...

查了一下递归，回溯，枚举感觉自己离我们系那些大神还差得好远
现在我有几个问题：1.回溯的话每次的情况需要控制不同，怎么控制，用if吗？只是我试了几次都失败实在没有          头绪 2.无限递归的话除非输出YES，否则只能等到满足超出6位数的条件来输出NO吗？ 烦扰了，确实需要大神的代码参考，不过我保证要自己写出来，不是复制粘贴

小山童鞋

honhon 发表于 2016-12-16 20:42
查了一下递归，回溯，枚举感觉自己离我们系那些大神还差得好远
现在我有几个问题：1.回溯的话 ...

我现在在刷其他题，最迟明天给你发代码，或者你可以加我QQ870817784.

人造人

直接贴代码行不行？
不知道还有没有潜在的bug

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. int is_prime_number_long_long(long long n)
   
6. {
   
7.         int i = 2;
   
8.         while(i<n)
   
9.         {
   
10.                 if(n%i == 0)
    
11.                 {
    
12.                         break;
    
13.                 }
    
14.                 i++;
    
15.         }
    
16. 
    
17.         if(i == n)
    
18.         {
    
19.                 return 1;
    
20.         }
    
21.         else
    
22.         {
    
23.                 return 0;
    
24.         }
    
25. }
    
26. 
    
27. int is_prime_number_str(char *begin, char *end)
    
28. {
    
29.         char buf[100];
    
30. 
    
31.         if(end - begin > 6) return 0;
    
32. 
    
33.         memcpy(buf, begin, end - begin + 1);
    
34.         buf[end - begin + 1] = '\0';
    
35. 
    
36.         long long number = atoll(buf);
    
37. 
    
38.         return is_prime_number_long_long(number);
    
39. }
    
40. 
    
41. int str_prime_number(char str[], int str_len)
    
42. {
    
43.         for(int i = 0; i < str_len; i++)
    
44.         {
    
45.                 for(int j = i; j < str_len; j++)
    
46.                 {
    
47.                         if(is_prime_number_str(&str[i], &str[j]) == 1) return 1;
    
48.                 }
    
49.         }
    
50. 
    
51.         return 0;
    
52. }
    
53. 
    
54. int main(void)
    
55. {
    
56.         char test_str[] = "1447160917891993";
    
57.         char test_str2[] = "999444";
    
58. 
    
59.         if(str_prime_number(test_str, strlen(test_str)) == 0)
    
60.         {
    
61.                 printf("NO\n");
    
62.         }
    
63.         else
    
64.         {
    
65.                 printf("YES\n");
    
66.         }
    
67. 
    
68.         if(str_prime_number(test_str2, strlen(test_str2)) == 0)
    
69.         {
    
70.                 printf("NO\n");
    
71.         }
    
72.         else
    
73.         {
    
74.                 printf("YES\n");
    
75.         }
    
76. 
    
77.         return 0;
    
78. }
    

复制代码

四十二

膜拜楼上

小山童鞋

给你参考下，搜索的写法。
我稍作修改了下，改成字符最多只能三位。原理是一样的。

1. #include<cstdio>
   
2. #include<string.h>
   
3. //数组a用来保存解，ai为数组a的下标
   
4. int a[1001] = {0};int ai=0;
   
5. //素数访问表，通过isprim数组查询是否为素数
   
6. int isnprim[1001]={0};
   
7. //处理isnprim数组
   
8. void deal()
   
9. {
   
10.     int i,j;isnprim[0]=1,isnprim[1]=1;
    
11.     for(i=2;i<1001;i++)
    
12.         for(j=i;j*i<1001;j++)
    
13.         isnprim[j*i]=1;
    
14. }
    
15. //把字符数组转换成十进制数并返回
    
16. int STI(char *sbeg,char *send)
    
17. {
    
18.     int n=0;
    
19.     while(sbeg<=send)
    
20.         n=n*10+*(sbeg++)-'0';
    
21.     return n;
    
22. }
    
23. //有解标志
    
24. int flag;
    
25. //寻找解的函数
    
26. int f(char *s)
    
27. {
    
28.     int len = strlen(s);
    
29.     int i;
    
30.     //如果越界就代表有解就打印解
    
31.     if(len<=0)
    
32.     {
    
33.         flag = 1;
    
34.         for(i=0;i<ai;i++)printf("%d ",a[i]);
    
35.         putchar('\n');
    
36.     }
    
37.     else
    
38.     {
    
39.         //搜索可行解
    
40.         for(i=0;i<3&&i<len;i++)
    
41.         {
    
42.             if(flag)return 1;
    
43.             a[ai] = STI(s,s+i);
    
44.             if(!isnprim[a[ai]])
    
45.             {
    
46.                 ai++;
    
47.                 f(s+i+1);
    
48.                 //回溯
    
49.                 ai--;
    
50.             }
    
51. 
    
52.         }
    
53.     }
    
54. }
    
55. 
    
56. int main()
    
57. {
    
58.     //调试用的文件
    
59.     //freopen("Input.txt","r",stdin);
    
60.     //freopen("Output.txt","w",stdout);
    
61.     deal();
    
62.     //将flag置0并调用f函数查询
    
63.     flag = 0;
    
64.     f("1331891995713193");
    
65.     if(flag)puts("YES");
    
66.     else puts("NO");
    
67.     return 0;
    
68. }

复制代码

honhon

小山童鞋 发表于 2016-12-16 23:51
给你参考下，搜索的写法。
我稍作修改了下，改成字符最多只能三位。原理是一样的。

谢谢，我会好好研究的

honhon

人造人 发表于 2016-12-16 21:42
直接贴代码行不行？
不知道还有没有潜在的bug

谢谢，我会好好研究的O(∩_∩)O

小山童鞋

你可以先去试着写一下排列组合的生成练练手。

小山童鞋

人造人 发表于 2016-12-16 21:42
直接贴代码行不行？
不知道还有没有潜在的bug

你可以试试这个“14471609178919934”

小山童鞋

honhon 发表于 2016-12-17 07:57
谢谢，我会好好研究的O(∩_∩)O

能不能发现这道题的链接，我去试试能不能A掉。

人造人

小山童鞋 发表于 2016-12-17 09:35
你可以试试这个“14471609178919934”

你指的是？

小山童鞋

这个是没办法构成解的

honhon

小山童鞋 发表于 2016-12-17 10:01
能不能发现这道题的链接，我去试试能不能A掉。

不知道是不是学校的原创，过阵子考试结束后再次开放，我可以帮你把码贴去试试（因为学校的Oj只允许学生提交题。。。。）

小山童鞋

我也是ACM的，大一的，创个帐号应该能提交的。。。。

下面的代码如果提交不能AC那我再改改。。

1. #include<cstdio>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. //数组a用来保存解，ai为数组a的下标
   
5. //int a[1001] = {0};int ai=0;
   
6. //素数访问表，通过isprim数组查询是否为素数
   
7. int isnprim[1000001]={0};
   
8. //处理isnprim数组
   
9. void deal()
   
10. {
    
11.     int i,j;isnprim[0]=1,isnprim[1]=1;
    
12.     for(i=2;i<1000001;i++)
    
13.         for(j=i;j*i<1000001;j++)
    
14.         {
    
15.             if(j*i<=0)
    
16.                 break;
    
17.             isnprim[j*i]=1;
    
18.         }
    
19. }
    
20. //把字符数组转换成十进制数并返回
    
21. int STI(char *sbeg,char *send)
    
22. {
    
23.     int n=0;
    
24.     while(sbeg<=send)
    
25.         n=n*10+*(sbeg++)-'0';
    
26.     return n;
    
27. }
    
28. //有解标志
    
29. int flag;
    
30. //寻找解的函数
    
31. int f(char *s)
    
32. {
    
33.     int len = strlen(s);
    
34.     int i;
    
35.     //如果越界就代表有解就打印解
    
36.     if(len<=0)
    
37.     {
    
38.         flag = 1;
    
39.         //for(i=0;i<ai;i++)printf("%d ",a[i]);
    
40.         //putchar('\n');
    
41.     }
    
42.     else
    
43.     {
    
44.         //搜索可行解
    
45.         for(i=0;i<6&&i<len;i++)
    
46.         {
    
47.             if(flag)return 1;
    
48.             //a[ai] = STI(s,s+i);
    
49.             if(!isnprim[STI(s,s+i)])
    
50.             {
    
51.                 //ai++;
    
52.                 f(s+i+1);
    
53.                 //回溯
    
54.                 //ai--;
    
55.             }
    
56.         }
    
57.     }
    
58. }
    
59. 
    
60. int main()
    
61. {
    
62.     //调试用的文件
    
63.     //freopen("Input.txt","r",stdin);
    
64.     //freopen("Output.txt","w",stdout);
    
65.     char s[1024];
    
66.     deal();
    
67.     while(~scanf("%s",s))
    
68.     {
    
69.         getchar();
    
70.         flag=0;
    
71.         f(s);
    
72.         if(flag)puts("YES");
    
73.         else puts("NO");
    
74.     }
    
75.     //将flag置0并调用f函数查询
    
76.     //flag = 0;
    
77.     //f("1447160917891993");
    
78.     //if(flag)puts("YES");
    
79.     //else puts("NO");
    
80.     return 0;
    
81. }

复制代码