台中女中b005

b005:熱門點播

方法一：不可行？

讀入n個數字，假設10個數字，且讀入的數字< MaxN(1000000)的話，

可以類似b002直接宣告陣列且在1~MaxN找出現最多的是哪一個

例如輸入： 10 55555 666 7777 99999 55555 333 22 111 55555 22則計數cnt[]陣列為：

索引	…	22	…	111	…	333	…	666	…	7777	…	55555	…	99999	…
計數		2		1		1		1		1		3		1

以下程式若點播編號 < 1000000 時可行{如以上資料}，但若讀入的編號 >= MaxN 則會錯誤

例如輸入： 10 55555 666 7777 99999 55555 333 22 111 55555 22222222

#include <iostream>

using namespace std;

const int MaxN = 1000000;

int cnt[MaxN];

int main(void)

{

        int j,n,k;

        for(j=1;j<MaxN;++j) cnt[j] = 0; //全設為 0 個

        cin >> n;

        for(j=0; j<n; ++j)

        {

                cin >> k; // 讀入的點播號， 若k=22222222，則 cnt[22222222]超出範圍

                cnt[k] ++;  //該號碼 計數 +1

        }

        int p=1, m=cnt[p] ; // 找出計數最大的編號及個數

        for(k=2; k<MaxN; ++k)

        {

                if( cnt[k] > m ) // 點播數較多的記住

                {

                        m = cnt[k] ;  //記住目前最多的個數

                        p=k;          // 記住點播號存至 p

                }

        }      

        cout <<p<< " " << m<< endl;

        return 0;

}

b005:熱門點播

方法二：如何解決以上的問題

例如輸入： 10 55555 666 7777 99999 55555 333 333 111 55555 22222222

改成兩個陣列，一個num存點播號，一個cnt存各點播號的計數，

而且，每個點播號依讀入的順序另編序號(索引)

num索引	0	1	2	3	4	5	6	…	19
num值	55555	666	7777	99999	333	111	22222222
cnt索引	0	1	2	3	4	5	6	…
cnt值	3	1	1	1	2	1	1	0	0

因為 n最大為20，所以num及cnt陣列不會超過20個元素

但如何將讀入的點播號轉成序號

{55555第1個:序號0、666第2個:序號1、…、第2次讀到55555出現過:使用序號0}

宣告一個變數 now為下一個序號值，一開始設為 0

每讀入一個點播號k 就檢查陣列num[0] ~ num[now-1] 是否已有 k 這個號碼

以下程式可完成這個任務

程式表頭，宣告部份就省略…

先將cnt陣列清空：for(i=0; i<20; ++i) cnt[i]=0;

讀入n： cin >> n;

接著迴圈讀入n個點播號k：   for(i=0; i<n; ++i) { 有五行程式碼，說明不算 }

(1)讀入k ：     cin >> k;

  (2)以迴圈j檢查num：           for(j=0; j<now; ++j)

  (3)   若k出現在num中跳出：      if(k==num[j]) break;        

     // 若 j<now 有出現過， 若 j==now 沒出現過

  (4)若沒出現過將k存入num陣列中，now+1：    if( j==now ) num[now++] = k;

  (5) 序號為 j 的編號 點播數加 1  ：    cnt[j]++ ;

    //  序號j ？ 因為若是j==now就是新的序號，或j<now就是找到曾出現的序號