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

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

#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[100];

        if(end - begin > 6) return 0;

        memcpy(buf, begin, end - begin + 1);
        buf[end - begin + 1] = '\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[i], &str[j]) == 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;
}

四十二

膜拜楼上

小山童鞋

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

#include<cstdio>
#include<string.h>
//数组a用来保存解，ai为数组a的下标
int a[1001] = {0};int ai=0;
//素数访问表，通过isprim数组查询是否为素数
int isnprim[1001]={0};
//处理isnprim数组
void deal()
{
    int i,j;isnprim[0]=1,isnprim[1]=1;
    for(i=2;i<1001;i++)
        for(j=i;j*i<1001;j++)
        isnprim[j*i]=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[i]);
        putchar('\n');
    }
    else
    {
        //搜索可行解
        for(i=0;i<3&&i<len;i++)
        {
            if(flag)return 1;
            a[ai] = STI(s,s+i);
            if(!isnprim[a[ai]])
            {
                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-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那我再改改。。

#include<cstdio>
#include<stdlib.h>
#include<string.h>
//数组a用来保存解，ai为数组a的下标
//int a[1001] = {0};int ai=0;
//素数访问表，通过isprim数组查询是否为素数
int isnprim[1000001]={0};
//处理isnprim数组
void deal()
{
    int i,j;isnprim[0]=1,isnprim[1]=1;
    for(i=2;i<1000001;i++)
        for(j=i;j*i<1000001;j++)
        {
            if(j*i<=0)
                break;
            isnprim[j*i]=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[i]);
        //putchar('\n');
    }
    else
    {
        //搜索可行解
        for(i=0;i<6&&i<len;i++)
        {
            if(flag)return 1;
            //a[ai] = STI(s,s+i);
            if(!isnprim[STI(s,s+i)])
            {
                //ai++;
                f(s+i+1);
                //回溯
                //ai--;
            }
        }
    }
}

int main()
{
    //调试用的文件
    //freopen("Input.txt","r",stdin);
    //freopen("Output.txt","w",stdout);
    char s[1024];
    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;
}