C语言解题思想

说说下面题目的解题思路：Problem description

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

(b1, b2,... bm -1, bm)

这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm -1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。

执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

Input

输入的第一行是一个整数T,表示测试数据的组数。对于每一组测试数据第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。

Output

对于每一组测试数据输出一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。

Sample Input
1
4
3 4
4 3
1 2
1 2

Sample Output
2

这是05年的NOIP的一道竞赛题，具体你查一下05年NOIP的解题报告
具体解法是这样的，先把环处理成一条链（枚举中间切断的地方）
然后虽然看似很难，但是实际很简单，剩下的工作就是进行一次
冒泡排序，注意只能冒泡，其它不行。最后M的值就是冒泡排序交换的
次数。

解题思路最简单的就是使用穷举法。但是如果先穷举所有的可能，再判断是否为可逆素数，那么运算量就太大了（共有1,853,020,188,851,841种可能）。所以我的想法是先求出所有的4位可逆素数，然后再进行穷举。 这道题有多个解，如果只需要1个解，那么还是很快的。如果要求出所有的解，那么就要花点时间了。附上我的代码。

#include <stdio.h>

int prime(int n) {     int i;     for(i = 2; i * i <= n; i++)         if(n % i == 0)             return 0;     return 1; }

int find(int ps[], int n, int x) {     int i;     for(i = 0; i < n; i++)         if(ps[i] == x)             return 1;     return 0; }

int judge(int ps[], int n, int i, int j, int k, int l) {     int m[6];     m[0] = ps[i] / 1000 * 1000 + ps[j] / 100 % 10 * 100 +            ps[k] / 10 % 10 * 10 + ps[l] % 10;     m[1] = ps[i] % 10 + ps[j] / 10 % 10 * 10 +            ps[k] / 100 % 10 * 100 + ps[l] / 1000 * 1000;     m[2] = ps[i] / 1000 * 1000 + ps[j] / 1000 * 100 +            ps[k] / 1000 * 10 + ps[l] / 1000;     m[3] = ps[i] / 100 % 10 * 1000 + ps[j] / 100 % 10 * 100 +            ps[k] / 100 % 10 * 10 + ps[l] / 100 % 10;     m[4] = ps[i] / 10 % 10 * 1000 + ps[j] / 10 % 10 * 100 +            ps[k] / 10 % 10 * 10 + ps[l] / 10 % 10;     m[5] = ps[i] % 10 * 1000 + ps[j] % 10 * 100 +            ps[k] % 10 * 10 + ps[l] % 10;     return find(ps, n, m[0]) && find(ps, n, m[1]) && find(ps, n, m[2]) &&            find(ps, n, m[3]) && find(ps, n, m[4]) && find(ps, n, m[5]); }

void print(int ps[], int i, int j, int k, int l) {     printf("succeed\n");     printf("%d\n", ps[i]);     printf("%d\n", ps[j]);     printf("%d\n", ps[k]);     printf("%d\n", ps[l]); }

int main() {     int ps[1000];     int i, j, k, l, x, y, c = 0;     for(i = 1; i <= 9; i++)         for(j = 1; j <= 9; j++)             for(k = 1; k <= 9; k++)                 for(l = 1; l <= 9; l++)                 {                     x = i * 1000 + j * 100 + k * 10 + l;                     y = i + j * 10 + k * 100 + l * 1000;                     if(!find(ps, c, x) && prime(x) && prime(y))                     {                         ps[c++] = x;                         ps[c++] = y;                     }                 }     for(i = 0; i < c; i++)         for(j = 0; j < c; j++)             for(k = 0; k < c; k++)                 for(l = 0; l < c; l++)                     if(judge(ps, c, i, j, k, l))                         print(ps, i, j, k, l);     return 0; }

至于你的代码我没有仔细去看，不过在前面就已经有错误了。 x3=1000*s[1][4]+100*s[2][3]+10*s[3][2]+s[1][4]; x4=1000*s[4][1]+100*s[3][2]+10*s[2][3]+s[4][1];

不是有要求么"如果无论怎么调整都不能符合每个同学的愿望，则输出-1。 " "

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。 如果3, 4, 5......n-1, n 的两个最希望相邻的同学都是1, 2，而1想和3，4 相邻，2也想和3，4相邻怎么办