720
『每日一題 2012-04-17』巧排數字
問題描述：
將1，2，3，……，20這20個連續的自然數排成一圈，使任意兩個相鄰的自然數之和均為素數
強人的思路：
1 找出所有和為素數的數對
2 找Hamilton環
找所有和為素數的數對的方法：
1，2，3，……，20任意兩數之和的最大值為39，可取40。故首先，我們找出1到40之間的所有素數，實現函數如下：
int create_prime(int *a, int max) // 找到 1 到 max 間的所有素數
{
int *x;
int i,j;
x = (int *)alloca(sizeof(int)*(max+1));
for(i=1;i<=max;i++) // initialize x[]
x[i] = 0;
x[2] = 1; // 2 是素數
for(i=3;i<=max;i+=2)
x[i] = 1;
for(i=3;i<max/3;i+=2)
for(j=i*3;j<=max;j+=2*i)
x[j] = 0;
j = 0;
for(i=0;i<=max;i++)
if(x[i] == 1)
a[j++] = i;
return j;
}
其中，數組a保存找到的1到40之間所有的素數，結果按下標順序從小到大保存。函數最後返回找到的素數的個數。
然後構建一個map（二維數組）來保存所有和為素數的數對，實現函數如下：
void create_map(void)
{
int a[20]; // 保存 1 ——40 之間的素數
int len; // 1 -- 40之間素數的個數
int i,j,k;
len = create_prime(a,40);
for(i=1;i<=20;i++) {
degree[i] = 0;
for(j=0;j<len;j++) {
k = a[j] - i;
if(k <=0)
continue;
if(k <= 20)
map[i][degree[i]++] = k;
else
break;
}
}
}
找Hamilton環的實現，就是回溯搜索（類似於堆棧）的方法，來找出所有符合條件的結果。
這裏要注意考慮清楚 前進 和回退 條件。實現為：
int main()
{
int i,j;
create_map();
for(i=1;i<=20;i++)
{
printf("%d:\t",i);
for(j=0;j<degree[i];j++)
{
printf("%d\t",map[i][j]);
}
printf("\n");
}
ham[0] = 1; // 第一個節點選擇的數字 為 1
ham_len = 1;
for(i=0;i<=20;i++)
{
cur_use[i] = 0;
cur_pos[i] = 0;
}
cur_use[1] = 1;
j = 1; //下個需要處理的數字
cur_pos[1] = 0;
while(1)
{
while(cur_pos[j]<degree[j])
{
if(cur_use[map[j][cur_pos[j]]] == 0) //找到了可用數字
{
cur_use[map[j][cur_pos[j]]] = 1;
ham[ham_len++] = map[j][cur_pos[j]];
break;
}
cur_pos[j]++;
}
if(cur_pos[j] < degree[j])
{
if(ham_len==20 && map[ham[19]][0]==1)
{
for(i=0;i<20;i++)
printf("%d->",ham[i]);
printf("\n");
system("pause");
}
else
{
j = ham[ham_len-1];
cur_pos[j] = 0;
continue;
}
}
if(--ham_len <= 0)
break;
cur_use[ham[ham_len]] = 0;
j = ham[ham_len-1];
cur_pos[j]++;
}
system("pause");
return 0;
}
最後更新：2017-04-02 22:16:36