c-不同手表的位置同步

Question

我试图解决以下问题，但没有成功：

你会得到16个时钟，它们都设置在1到12之间的某个位置。初始配置为：

12, 9, 3, 12, 6, 6, 9, 3, 12, 9, 12, 9, 12, 12, 6, 6

你会得到一组切换线路：

# define max_switch 10
int switchLines[max_switch][5] =
{
    {0,1,2,-1,-1},
    {3,7,9,11,-1},
    {4,10,14,15,-1},
    {0,4,5,6,7},
    {6,7,8,10,12},
    {0,2,14,15,-1},
    {3,14,15,-1,-1},
    {4,5,7,14,15},
    {1,2,3,4,5},
    {3,4,5,9,13}
};

将忽略等于-1的条目。按下开关时，开关行中列出的时钟值将增加3。

例如，按下初始配置中的第一个开关将产生：

3, 12, 6, 12, 6, 6, 9, 3, 12, 9, 12, 9, 12, 12, 6, 6

您可以按任意顺序按任意开关任意次数。

将所有时钟设置为12所需的最小开关按下次数是多少？

我正在寻找一种算法来解决上述问题。

以下是我正在尝试的解决方案

#include <stdio.h>
#include <stdlib.h>
int clock1[16] ={12, 9, 3, 12 ,6, 6 ,9 ,3 ,12, 9, 12, 9 ,12 ,12, 6 ,6};
int swicthApplied = 0;
#define mac_sw 10
int switchLink[mac_sw][5]=
{
    {0,1,2,-1,-1},
    {3,7,9,11,-1},
    {4,10,14,15,-1},
    {0,4,5,6,7},
    {6,7,8,10,12},
    {0,2,14,15,-1},
    {3,14,15,-1,-1},
    {4,5,7,14,15},
    {1,2,3,4,5},
    {3,4,5,9,13}
};
int isSwicthRequired()
{
int i=0, need = 0;
for(i=0;i<16;i++)
{
    if(clock1[i] <  12)
    {
        need = 1;
    }
}
return need;
 }
 int findmax(int array[], int size)
 {
int   maximum, c, location = 0;
maximum = array[0];
if(array[0] == 0) location = -2;
for (c = 1; c < size; c++)
{
    if (array[c] > maximum)
    {
        maximum  = array[c];
        location = c  ;
    }
}
return location +1;
}
runSwicth(int pos)
{
int i =0;
for(i=0;i<5;i++)
{
    int valu = switchLink[pos][i];
    if(valu == -1 ) continue;
    if(clock1 [valu] == 12)
    {
         // continue;
         clock1 [valu] = 3;
    }
    else
        clock1 [valu] = clock1[valu] +  3;
 }
 printClock(clock1,16);
 swicthApplied = 1 + swicthApplied;
//exit(0);
}
int findBestMatchSwitch( void)
{
//if(maxSwicth >=10) return -1;
 int maxSwicth = mac_sw,numberofSwicths = 5,i,j;
 int array[10] = {0,0,0,0,0,0,0,0,0,0};
for( i = 0;i<maxSwicth;i++)
{
    for(j=0;j<numberofSwicths;j++)
    {
        int pos = switchLink[i][j] ;
        if(pos == -1) continue;
        if(clock1[pos] != 12)
        {
            array[i] = array[i] +1;
        }
    }
}
int loc = findmax(array,10);
if(loc == -1) return -1;
applySwicth(loc -1);
//omitLoc[loc-1] = -1;
return 0;
//exit(0);
}

 int runAlignment()
{
int need =0;
while(1)
{
    need = isSwicthRequired();
    if (need ==0) break;
    if(findBestMatchSwitch() == -1)
    {
        return -1;
    }
}
return need;
}


 int main(void) {
runAlignment();
printf("Swicthes Required [%d]",swicthApplied);
//getClockneed();
//printClock(clockNeed,16);
return EXIT_SUCCESS;
}

Answer 1

根据定义，解决方案是长度最小的开关列表，这样，当按顺序按下开关时，初始配置将转换为所需配置。

请注意，按下开关的顺序实际上并不重要。还要注意，在最小解决方案中，开关的按下次数不得超过三次。

因此，对于十个开关中的每一个，您都有四个选择（0到3次按压）需要考虑，即需要检查的可能性总数为4^10或大约一百万。