同步

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或大約一百萬。