Programming－寻找发贴水王（C）

╰+攻爆jí腚メ 2023-01-19 12:49 8阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

/*
     * 在某一论坛，坊间风闻有一“水王”发帖数目超过了帖子总数的一半。你能快速找出这个传说中的水王吗？
     *
     * PostWaterKing.c - by Peace
     */
    
    #include <stdio.h>
    
    typedef int Type;
    
    Type Find(Type* ID, int N)
    {
    	Type candidate = -1;
    	int nTimes, i;
    	for (i = nTimes = 0; i < N; i++)
    	{
    		if (nTimes == 0)
    		{
    			candidate = ID[i];
    			nTimes = 1;
    		}
    		else
    		{
    			if (ID[i] == candidate)
    			{
    				nTimes++;
    			}
    			else
    			{
    				nTimes--;
    			}
    		}
    	}
    	return candidate;
    }
    
    /*
     * 继上次水王找到之后，论坛江湖又过了一段时间，现又涌现出三个发帖很多的ID，
     * 他们的发帖数目都超过了帖子总数目N的1/4。怎么从发贴的ID中快速找出他们的ID？
     */
    Type* Find3(Type* ID, int N)
    {
    	Type candidate[3] = { -1, -1, -1 };
    	int nTimes[3] = { 0, 0, 0 };
    	int i;
    	for (i = 0; i < N; i++)
    	{
    		if (nTimes[0] == 0)
    		{
    			candidate[0] = ID[i];
    			nTimes[0] = 1;
    		}
    		else if (nTimes[1] == 0)
    		{
    			candidate[1] = ID[i];
    			nTimes[1] = 1;
    		}
    		else if (nTimes[2] == 0)
    		{
    			candidate[2] = ID[i];
    			nTimes[2] = 1;
    		}
    		else if (ID[i] == candidate[0])
    		{
    			nTimes[0]++;
    		}
    		else if (ID[i] == candidate[1])
    		{
    			nTimes[1]++;
    		}
    		else if (ID[i] == candidate[2])
    		{
    			nTimes[2]++;
    		}
    		else
    		{
    			nTimes[0]--;
    			nTimes[1]--;
    			nTimes[2]--;
    		}
    	}
    	return candidate;
    }
    
    main()
    {
    	Type A[16] = { 1, 6, 3, 6, 6, 2, 1, 6, 6, 3, 6, 6, 3, 6, 1, 6 };
    	printf("The water king is: %d\n", Find(A, 16));
    
    	Type A3[40] =
    	{
    		1,5,1,88,3,2,3,2,3,3,
    		3,2,6,9,99,3,2,1,1,1,
    		2,1,3,3,2,1,66,6,3,1,
    		1,2,11,1,2,3,2,2,2,3
    	};
    	Type* K = Find3(A3, 40);
    	printf("Afterwards, the big 3 water kings are: %d %d %d\n", K[0], K[1], K[2]);
    
    	return 0;
    }
    
    // Output:
    /*
    The water king is: 6
    Afterwards, the big 3 water kings are: 3 2 1
    
    */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter