CSDN看见的一道面试题

一共有上下两排数，上排的十个数是【0，1，2，3，4，5，6，7，8，9】
针对上排的每个数，在其对应的下面位置填写一个数，该数表示其在下面出现的次数。
如：
数值:0,1,2,3,4,5,6,7,8,9
分配:6,2,1,0,0,0,1,0,0,0

 

 

#include <iostream>

using namespace std;

const int N = 10;
int source[N];
int dest[N] = {0};

void init()
{
    for(int i=0; i<N; i++)
    {
        source[i] = i;
    }
}

void display(int target[])
{
    for(int i=0; i<N; i++)
    {
        printf("%4d", target[i]);
    }
    cout << endl;
}

int execute()
{
    int edit = 0;
    
    for(int i=0; i<N; i++)
    {
        int temp = 0;
        for(int j=0; j<N; j++)
        {
            if(dest[j] == source[i])
            {
                temp++;
            }
        }
        if(temp == dest[i])
        {
            
        }
        else
        {
            edit++;
            dest[i] = temp;
        }
    }
    return edit;
}

void main()
{
    int edit = 1,counts = 0;
    init();
    display(source);
    while(edit)
    {
        counts++;
        edit = execute();
        //display(dest); 打印每次执行后的轨迹

        if(counts > N + 1)
        {
            cout << "无解" << endl;
            break;
        }
    }
    display(dest); // 最后结果

}

原理很简单，就是对dest[]不停的遍历，有edit作为标志位，如果edit=0，则表示dest[]已经平衡了，跳出循环。

不过对于无解的情况，直接给出的就是整个遍历次数大于N+1，没有证明过，应该没问题