程序在元素求和和移动的条件下对数组进行排序 [英] Program to sort an array under conditions on sum and movement of elements
问题描述
系统会为您提供1x到3x3的数字数组. 在每个步骤中，如果两个相邻的块的总和是质数，则可以交换它们.如果两个图块具有相同的边缘，则认为它们是相邻的.
You are given a 3x3 array of numbers from 1-9. At each step, you may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.
这是来自以下方面的问题: http://www.codechef.com/problems/H1
This is a problem from: http://www.codechef.com/problems/H1
我制作了这个程序，该程序按照给定的规则对给定的数组进行排序.对于最小翻转数为7的数组/拼图，它可以工作.但是对于最小翻转次数超过此次数的数组/拼图，则不起作用.
I made this program which sorts the given array following the given rules. For arrays/puzzles with number of minimum flips=7, it works. but for arrays/puzzles with minimum flips more than that it does not work.
#include <stdio.h>
#include <stdlib.h>
int a[9]={6,3,5,4,7,2,1,9,8};
//6,3,5,7,9,4,1,8,2
int b[9]={0};
int c[9]={0};
int d[9]={0};
int e[9]={0};
int sortcond=0,count=0;
typedef struct Queue
{
int capacity;
int size;
int front;
int rear;
int *elements;
}Queue;
Queue * createQueue(int maxElements)
{
Queue *Q;
Q = (Queue *)malloc(sizeof(Queue));
Q->elements = (int *)malloc(sizeof(int)*maxElements);
Q->size = 0;
Q->capacity = maxElements;
Q->front = 0;
Q->rear = -1;
return Q;
}
void Dequeue(Queue *Q)
{
if(Q->size==0)
{
printf("Queue is Empty\n");
return;
}
else
{
Q->size--;
Q->front++;
if(Q->front==Q->capacity)
{
Q->front=0;
}
}
return;
}
int front(Queue *Q)
{
if(Q->size==0)
{
printf("Queue is Empty\n");
exit(0);
}
return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
if(Q->size == Q->capacity)
{
printf("Queue is Full\n");
}
else
{
Q->size++;
Q->rear = Q->rear + 1;
if(Q->rear == Q->capacity)
{
Q->rear = 0;
}
Q->elements[Q->rear] = element;
}
return;
}
void enqueue(Queue *Q,int *element)
{
int i;
if(Q->size == Q->capacity)
{
printf("Queue is Full\n");
}
else
{
for(i=0;i<9;i++){
Q->size++;
Q->rear = Q->rear + 1;
if(Q->rear == Q->capacity)
{
Q->rear = 0;
}
Q->elements[Q->rear] = *(element+i);
}
}
return;
}
void EnQueue(Queue *Q,int *element)
{
int i;
if(Q->size == Q->capacity)
{
printf("Queue is Full\n");
}
else
{
Q->elements[Q->rear] = *element;
for(i=1;i<9;i++){
Q->size++;
Q->rear = Q->rear + 1;
if(Q->rear == Q->capacity)
{
Q->rear = 0;
}
Q->elements[Q->rear] = *(element+i);
}
}
return;
}
Queue *que,*seen;
int primecheck(int num1,int num2){
switch(num1+num2){
case 3:
case 5:
case 7:
case 11:
case 13:
case 17:
return 1;
}
return 0;
}
int possibleflips(){
int validpair[12][2] = { {0,1}, {1,2}, {3,4}, {4,5}, {6,7}, {7,8}, {0,3}, {3,6}, {1,4}, {4,7}, {2,5}, {5,8} };
int i,j,p,q,temp,seencond,seencond2;
//printf("entered possibleflips\n");
for(i=0;i<12;i++){
int p = validpair[i][0];
int q = validpair[i][1];
if(primecheck(b[p],b[q])){
for(j=0;j<9;j++){
c[j]=b[j];
}
temp=c[p];
c[p]=c[q];
c[q]=temp;
while(front(seen)!=0){
seencond=1;
seencond2=0;
for(j=0;j<9;j++){
d[j]=front(seen);
if(c[j]==front(seen));
else
seencond=0;
Dequeue(seen);
}
enqueue(seen,d);
if(seencond==1){
seencond2=1;
}
}
if(seencond2==0){
EnQueue(seen,c);
Enqueue(seen,0);
enqueue(que,c);
}
else{
Dequeue(seen);
Enqueue(seen,0);
}
}
}
//printf("exit possibleflips\n");
return;
}
int searching(){
int i,cond;
//printf("entered search\n");
while(front(que)!=0){
cond=1;
for(i=0;i<9;i++){
e[i]=front(que);
if(front(que)==i+1);
else
cond=0;
Dequeue(que);
}
enqueue(que,e);
if(cond==1){
sortcond=1;
return;
}
}
Dequeue(que);
Enqueue(que,0);
//printf("exit search\n");
return;
}
int firststep(){
int i;
//printf("firststep\n");
while(sortcond==0){
while(front(que)!=0){
for(i=0;i<9;i++){
b[i]=front(que);
//printf("%d ",b[i]);
Dequeue(que);
}
//printf("\n");
possibleflips();
}
Dequeue(que);
Enqueue(que,0);
searching();
count++;
}
return;
}
int main()
{
int i;
que=createQueue(5000000);
seen=createQueue(5000000);
enqueue(que,a);
Enqueue(que,0);
enqueue(seen,a);
Enqueue(seen,0);
firststep();
printf("count %d", count);
return 0;
}
a []是给定的数组(您可以放置一些简单的问题，例如1,3,2,4,5,6,7,8,9)，并且适用于它们.
a[] is the given array (you can put some simple problem like 1,3,2,4,5,6,7,8,9) and it works for them.
它首先将给定的数组添加到队列中，找到可以在给定数组上一次交换的阵列，然后将它们添加到队列中并从队列中删除给定的数组.搜索其中是否有1,2..9.如果不是，那么它将找到您可以进行一次交换的阵列，即与给定阵列交换两次，然后将它们添加到队列中，依此类推.它还会检查案件是否重复.
it first adds the given array to queue and, finds the arrays you can make in one swap on the given array and adds them to queue and removes the given array from the queue. searches if any of them makes it 1,2..9. If not, then it finds the arrays you can make in one more swap, i.e. two swaps away from the given array, and adds them to queue and so on. It also checks for the repetition of cases.
适用于最少翻转次数小于7的数组，例如{6,3,5,7,9,4,1,8,2}.但对于最少翻转次数大于此次数的数组，例如{6,3,5,4,7,2,1,9,8}，它不起作用.
Works fine for arrays with minimum number of flips under 7 e.g. {6,3,5,7,9,4,1,8,2}. but for arrays with minimum number of flips more than that, e.g. {6,3,5,4,7,2,1,9,8}, it is not working.
推荐答案
我无法遍历您提供的全部代码，但据我所知，您不会检查部分结果的唯一性:您永远不会知道是否已经检查了板状态.结果，您的代码来回翻转相同，多次重复相同的分析.相同的板状态一次又一次地排队，导致数据结构溢出.
I couldn't go through the whole code you gave, but as far as I could understand it, you don't check partial results for uniqueness: you never know if the board state has already been checked. As a result your code makes the same flips to and fro, repeating the same analysis multiple times. The same board states are enqueued again and again, resulting in data structure overflow.
添加另一个队列，例如. Queue *seen;，以测试所有数字的排列，并检查posflips()中每个新的排列是否已在seen中.如果是这样，则忽略该排列，否则将其同时添加到qu和seen.
Add another queue, eg. Queue *seen;, to keep all numbers' permutations tested, and check every new permuttion in posflips() if it is already in seen. If so, ignore the permutation, else add it both to qu and to seen.
PS.
您知道数字只是1到9，所以两个数之和可以是3到17，因此只有6个可能的质数，您的primecheck()可以简化为
PS.
You know the numbers are 1 to 9 only, so the sum of two can be 3 to 17, consequently there are only 6 possible primes and your primecheck() can be simplified to
int primecheck(int numloc1,int numloc2){
switch(numloc1+numloc2){
case 3:
case 5:
case 7:
case 11:
case 13:
case 17:
return 1;
}
return 0;
}
您的电路板上总共有36对磁贴，其中只有12对是相邻磁贴.因此，在posflips()中完成的primecheck()调用的2/3是没有用的.您应该首先调用check()，并且只有在调用成功后才调用primecheck()，如下所示:
There are 36 total pairs of tiles in your board and only 12 of them are pairs of adjacent tiles. So 2/3 of primecheck() invocations done in posflips() are useless. You should call check() first and only if it succeedes call primecheck(), like this:
if(check(i,j) && primecheck(c[i],c[j])){
//....
}
此外，您完全可以摆脱check().您的董事会规模很小，因此枚举所有有效的职位对可能比测试每对职位的有效性都容易:
In addidtion, you can get rid of check() at all. Your board is quite small, so it might be easier to enumerate all valid pairs of positions than test every pair for validity:
int validPair[12][2] = {
{0,1}, {1,2}, {3,4}, {4,5}, {6,7}, {7,8},
{0,3}, {3,6}, {1,4}, {4,7}, {2,5}, {5,8}
};
int p;
for(p=0;p<12;p++){
int i = validPair[p][0];
int j = validPair[p][1];
if(primecheck(c[i],c[j])){
// ... do flips
// ... check flipped board against 'seen' queue
// ... and Enqueue if the board not seen before
}
编辑
如果将seencond重命名为arraysAreEqual，并且将seencond2重命名为arrayWasSeen，则初始化将变得非常明显
If you rename seencond to arraysAreEqual and seencond2 to arrayWasSeen it will become quite obvious the initialization
arrayWasSeen=0;
以前
seencond2=0;
应该在while循环之前之前.
注意:在单独的位置构造翻转数组时，不需要temp变量–只需交叉复制原始数组中的两个项目即可:
Note: as you construct a flipped array in a separate place, you don't need temp variable – just cross-copy the two items from the original array:
for(j=0;j<9;j++)
c[j]=b[j];
c[p]=b[q];
c[q]=b[p];
这篇关于程序在元素求和和移动的条件下对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
