微軟等數據結構與算法面試100題 第六題

第六題
題目：
給你10分鐘時間，根據上排給出十個數，在其下排填出對應的十個數
要求下排每個數都是先前上排那十個數在下排出現的次數。
上排的十個數如下：
【0，1，2，3，4，5，6，7，8，9】

分析：這道題拿到題目第一感覺是使用迭代算法計算，終止條件是求解得到上面的解。
如果使用迭代算法，會造成一下兩個問題：1，迭代算法不能夠保證收斂，因此可能陷入死循環，或者說是收斂不到解。2，迭代算法不能夠求解全部的解，只能得到滿足該
條件的一個解。

使用迭代算法的代碼如下：
[cpp] 
#include<iostream> 
#include<stdio.h> 
using namespace std; 
 
bool timeNoOf(int * timeNoOf, int * Array, const int length) 
{ 
    bool success = true; 
    for(int i = 0; i < length; i++) timeNoOf[i] = 0; 
    for(int i = 0; i < length; i++) 
    { 
        timeNoOf[Array[i]] = timeNoOf[Array[i]] + 1; 
    } 
    for(int i = 0; i < length; i++) 
    { 
        if(timeNoOf[i]!=Array[i]) 
        { 
            success = false; 
            Array[i] = timeNoOf[i]; 
        } 
 
    } 
    //int sum=0; 
    //for(int i=0; i<length-1; i++) sum = sum + Array[i]; 
    //Array[length-1] = length - sum; 
    return success; 
} 
 
 
 
void timesNoArray(int *a, int * timeNo, const int length) 
{ 
     
    for(int i=0; i < length; i++) timeNo[i] = 0; 
    bool success = false; 
    while(!success){ 
        //update the timeNo array 
        success = timeNoOf(timeNo, a, length); 
        for(int i =0; i < 10; i++ ) cout<< timeNo[i]<<" "; 
        cout<<endl; 
    } 
     
} 
 
 
int main() 
{ 
    int a[] = {0,1,2,3,4,5,6,7,8,9}; 
 
    int b[] = {0,1,2,3,4,5,6,7,8,9}; 
 
    timesNoArray(a,b,10); 
 
    for(int i =0; i < 10; i++ ) cout<< b[i]<<" "; 
 
    return 0; 
} 

在測試例子的時候，發現當n=10，即十個數如 0  1 2 3 4 5 6 7 8 9時候會在兩個解之間擺動，但是收斂不到需要求解的解。
其它更好的求解算法待後續補充！也請各位大牛指正！