• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            HDOJ 1016 Prime Ring Problem

            Problem Description
            A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

            Note: the number of first circle should always be 1.


             

            Input
            n (0 < n < 20).
             

            Output
            The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

            You are to write a program that completes above process.

            Print a blank line after each case.
             

            Sample Input
            6
            8
             

            Sample Output
            Case 1:
            1 4 3 2 5 6
            1 6 5 2 3 4
            Case 2:
            1 2 3 8 5 6 7 4
            1 2 5 8 3 4 7 6
            1 4 7 6 5 8 3 2
            1 6 7 4 3 8 5 2
                素數環:由1到n個數構成一個環,其中環內任意2個相鄰的數字之和是素數。
                比較經典的搜索題,由于n<20,可以先預處理出前40個自然數中的素數,然后深搜某個位置的未被訪問過的數字和它相鄰位置的數字之和是否為素數,搜索退出的條件為最后一個位置的數字circle[n]+1是否為素數。一次搜索完成后,要回溯,否則只會輸出一組解。
            #include <iostream>
            using namespace std;

            const int MAXN = 41;
            bool visit[MAXN];
            int n,p[MAXN],circle[MAXN];

            void prime(){
                
            int i,j;
                memset(p,
            true,sizeof(p));
                
            for(i=2;i<MAXN;i++)
                    
            for(j=2;i*j<MAXN;j++)
                        p[i
            *j]=false;
            }

            void dfs(int c,int cnt){
                
            if(cnt==&& p[circle[1]+circle[n]]){
                    
            for(int i=1;i<n;i++)
                        printf(
            "%d ",circle[i]);
                    printf(
            "%d\n",circle[n]);
                }

                
            for(int i=c+1;i<MAXN;i++)
                    
            if(p[i] && i-c<=&& !visit[i-c]){
                        circle[cnt
            +1]=i-c;
                        visit[i
            -c]=true;
                        dfs(i
            -c,cnt+1);
                        visit[i
            -c]=false;
                    }

            }

            int main(){
                
            int c=1;
                prime();
                
            while(scanf("%d",&n)!=EOF){
                    memset(visit,
            false,sizeof(visit));
                    printf(
            "Case %d:\n",c++);
                    visit[
            1]=true,circle[1]=1;
                    dfs(
            1,1);
                    printf(
            "\n");
                }

                
            return 0;
            }

            posted on 2009-05-24 13:37 極限定律 閱讀(1174) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC

            評論

            # re: HDOJ 1016 Prime Ring Problem 2009-08-04 09:53

            謝了 !?。。。。。。。?!1  回復  更多評論   

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            婷婷综合久久中文字幕| 久久亚洲精品无码aⅴ大香| 久久精品国产精品青草app| 四虎国产精品免费久久5151| 久久久久久久久久久免费精品| 武侠古典久久婷婷狼人伊人| 久久国产精品成人片免费| 久久久精品国产Sm最大网站| 一本久久a久久精品亚洲| 色综合久久综合网观看| 久久久无码精品亚洲日韩蜜臀浪潮| 久久男人Av资源网站无码软件| 精品久久久久一区二区三区| 久久男人Av资源网站无码软件| 麻豆久久| 久久男人AV资源网站| 久久精品免费观看| 久久久久99精品成人片试看| 久久久国产精华液| 人人狠狠综合久久亚洲| 7国产欧美日韩综合天堂中文久久久久 | 亚洲AV日韩精品久久久久久久| 欧美日韩中文字幕久久伊人| 久久影院综合精品| 性做久久久久久久| 人妻无码精品久久亚瑟影视 | 久久久精品久久久久久| AV狠狠色丁香婷婷综合久久 | 免费观看久久精彩视频| 亚洲AV日韩精品久久久久久| 99久久精品免费看国产一区二区三区 | 久久精品国产男包| 精品一二三区久久aaa片| 久久综合九色欧美综合狠狠| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久精品国产亚洲AV电影| 久久精品国产亚洲AV麻豆网站 | 久久国产精品免费一区二区三区| 亚洲国产精品久久久久| 2020最新久久久视精品爱 | 亚洲国产精品无码久久SM|