c - 不同 watch 位置同步

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

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

请注意，按下开关的顺序实际上并不重要。另请注意，在最小解决方案中，没有开关被按下超过 3 次。

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