一道竞赛题，想了两天无果，虽然考试结束，我还是希望得到指点,C\C++交流,技术交流,鱼C论坛

honhon 发表于 2016-12-16 08:47:14

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

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

再例如
999444
输出NO

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

conn 发表于 2016-12-16 11:53:10

还没看懂，晚上看看

honhon 发表于 2016-12-16 12:20:59

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

嗯嗯，谢谢{:10_254:}

小山童鞋 发表于 2016-12-16 16:47:09

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

我看看明天把代码贴上来

小山童鞋 发表于 2016-12-16 16:49:05

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

honhon 发表于 2016-12-16 20:16:35

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

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

honhon 发表于 2016-12-16 20:42:28

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

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

小山童鞋 发表于 2016-12-16 21:35:21

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

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

人造人 发表于 2016-12-16 21:42:16

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int is_prime_number_long_long(long long n)
{
int i = 2;
while(i<n)
{
if(n%i == 0)
{
break;
}
i++;
}

if(i == n)
{
return 1;
}
else
{
return 0;
}
}

int is_prime_number_str(char *begin, char *end)
{
char buf;

if(end - begin > 6) return 0;

memcpy(buf, begin, end - begin + 1);
buf = '\0';

long long number = atoll(buf);

return is_prime_number_long_long(number);
}

int str_prime_number(char str[], int str_len)
{
for(int i = 0; i < str_len; i++)
{
for(int j = i; j < str_len; j++)
{
if(is_prime_number_str(&str, &str) == 1) return 1;
}
}

return 0;
}

int main(void)
{
char test_str[] = "1447160917891993";
char test_str2[] = "999444";

if(str_prime_number(test_str, strlen(test_str)) == 0)
{
printf("NO\n");
}
else
{
printf("YES\n");
}

if(str_prime_number(test_str2, strlen(test_str2)) == 0)
{
printf("NO\n");
}
else
{
printf("YES\n");
}

return 0;
}

四十二 发表于 2016-12-16 22:38:04

膜拜楼上

小山童鞋 发表于 2016-12-16 23:51:07

本帖最后由小山童鞋于 2016-12-17 00:10 编辑

给你参考下，搜索的写法。
我稍作修改了下，改成字符最多只能三位。原理是一样的。
#include<cstdio>
#include<string.h>
//数组a用来保存解，ai为数组a的下标
int a = {0};int ai=0;
//素数访问表，通过isprim数组查询是否为素数
int isnprim={0};
//处理isnprim数组
void deal()
{
int i,j;isnprim=1,isnprim=1;
for(i=2;i<1001;i++)
   for(j=i;j*i<1001;j++)
   isnprim=1;
}
//把字符数组转换成十进制数并返回
int STI(char *sbeg,char *send)
{
int n=0;
while(sbeg<=send)
   n=n*10+*(sbeg++)-'0';
return n;
}
//有解标志
int flag;
//寻找解的函数
int f(char *s)
{
int len = strlen(s);
int i;
//如果越界就代表有解就打印解
if(len<=0)
{
   flag = 1;
   for(i=0;i<ai;i++)printf("%d ",a);
   putchar('\n');
}
else
{
   //搜索可行解
   for(i=0;i<3&&i<len;i++)
   {
         if(flag)return 1;
         a = STI(s,s+i);
         if(!isnprim])
         {
            ai++;
            f(s+i+1);
            //回溯
            ai--;
         }

   }
}
}

int main()
{
//调试用的文件
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
deal();
//将flag置0并调用f函数查询
flag = 0;
f("1331891995713193");
if(flag)puts("YES");
else puts("NO");
return 0;
}

honhon 发表于 2016-12-17 07:55:59

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

谢谢，我会好好研究的{:10_291:}

honhon 发表于 2016-12-17 07:57:27

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

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

小山童鞋 发表于 2016-12-17 09:04:02

本帖最后由小山童鞋于 2016-12-17 09:05 编辑

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

小山童鞋 发表于 2016-12-17 09:35:09

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

你可以试试这个“14471609178919934”

小山童鞋 发表于 2016-12-17 10:01:08

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

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

人造人 发表于 2016-12-17 12:47:14

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

你指的是？

小山童鞋 发表于 2016-12-17 14:08:13

这个是没办法构成解的

honhon 发表于 2016-12-17 17:00:58

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

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

小山童鞋 发表于 2016-12-17 18:39:34

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

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

#include<cstdio>
#include<stdlib.h>
#include<string.h>
//数组a用来保存解，ai为数组a的下标
//int a = {0};int ai=0;
//素数访问表，通过isprim数组查询是否为素数
int isnprim={0};
//处理isnprim数组
void deal()
{
int i,j;isnprim=1,isnprim=1;
for(i=2;i<1000001;i++)
   for(j=i;j*i<1000001;j++)
   {
         if(j*i<=0)
            break;
         isnprim=1;
   }
}
//把字符数组转换成十进制数并返回
int STI(char *sbeg,char *send)
{
int n=0;
while(sbeg<=send)
   n=n*10+*(sbeg++)-'0';
return n;
}
//有解标志
int flag;
//寻找解的函数
int f(char *s)
{
int len = strlen(s);
int i;
//如果越界就代表有解就打印解
if(len<=0)
{
   flag = 1;
   //for(i=0;i<ai;i++)printf("%d ",a);
   //putchar('\n');
}
else
{
   //搜索可行解
   for(i=0;i<6&&i<len;i++)
   {
         if(flag)return 1;
         //a = STI(s,s+i);
         if(!isnprim)
         {
            //ai++;
            f(s+i+1);
            //回溯
            //ai--;
         }
   }
}
}

int main()
{
//调试用的文件
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
char s;
deal();
while(~scanf("%s",s))
{
   getchar();
   flag=0;
   f(s);
   if(flag)puts("YES");
   else puts("NO");
}
//将flag置0并调用f函数查询
//flag = 0;
//f("1447160917891993");
//if(flag)puts("YES");
//else puts("NO");
return 0;
}

页: [1] 2

鱼C论坛's Archiver

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