题目来自网友分享:腾讯算法面试题 算法与代码

题目如下:

给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数。要求下排每个数都是先前上排对应那个数在下排十个数中出现的次数。

上排的十个数如下:

【0,1,2,3,4,5,6,7,8,9】

题目是比较简单的,我用C语言实现如下(引文中有java实现),其中输出中间过程的结果,最后输出总次数:

#include <stdio.h>
#define N 10

int temp[N];

void printTag(int tag){
     printf("-----Tag %d------\n", tag); 
     int i; 
     for(i=0; i<N; i++) 
                printf("%d ", temp[i]); 
     printf("\n"); 
} 
 
int getNew(int index){ 
        int n = 0; 
        int i; 
        for(i=0; i<N; i++) 
                if(temp[i] == index) 
                        n++; 
        return n; 
} 
 
int main(int argc, char** argv) { 
        int chs, i, newN, count = 0; 
        for(i=0; i<N; i++) 
                temp[i] = i; 
        printTag(0); 
        while(++count) { 
                chs = 0; 
                for(i=0; i<N; i++){ 
                    newN = getNew(i); 
                    if(newN != temp[i]) 
                        chs = 1; 
                        temp[i] = newN; 
                } 
                if(chs==0){ 
                    printf("\nIt takes %d times.\n", count-1); 
                        return 0; 
            } 
            printTag(count); 
        } 
} 

这里我把10设作常量N,N是可以改变的,只要N大于3。若N为1、2,无意义,若N为3,效果等于N=4,但不能直接将程序中N设作3,不然会有死循环。

多试几个N值,就会发现一个通用的规律,即:

0位对应N-4,1位对应2,2位对应1,N-4位对应1,其他位对应0。

引文中提到“这个算法可以用到数据压缩领域”,我暂时没有想清楚这是如何实现,不知大家没有想法?

如非说明转载,本博文章皆为原创,转载请务必注明文章出处: 转载自慎思琐识录 作者:慎思

本文链接地址: 一个有趣的编号问题的C语言实现

关于 Shens

Shens 已经在这个博客中伪文艺了 58 篇博文.

爱哲学,爱历史,也爱诗言志;爱读书,爱生活,也爱到处跑。我是非典型挨踢男。