0293-2016 名情复 编程 P317

编程语言基础 C语言 算法

$0$ から $V-1$ までの整数値が出るくじを $N$ 回引いた。$N,V$ はそれぞれ $1$ 以上の整数の定数とする。この結果における各値の出現回数を表示し，さらに，出現回数に比例した確率で値を $1$ つ選んで表示することでくじ引きを再現する C 言語のプログラムを以下の手順で作成した。各問いに答えよ。なお，以下では $N$ を $6,V$ を $3$，くじを引いて出た値を “$1,2,0,1,2,1$” とする。

[1] まず，くじを引いた結果における各値の出現回数を計算して表示する以下のプログラムを作成した。関数 calcDist は，くじを引いた結果の値が代入された大きさ $N$ の整数型 1 次元配列と，大きさ $V$ の整数型 1 次元配列の先頭要素のアドレスを，整数型ポインタ変数 dat, dis でそれぞれ受け取る。そして，計算結果として，dat が指す配列の要素における値 $x$ の出現回数を，dis が指す配列の $x$ 番目の要素の値として設定する。適切に動作し実行結果の通りの出力を得るように空欄を埋めよ。

プログラム：

#include <stdio.h>
#include <stdlib.h>
#define N 6
#define V 3
 
void calcDist(int *dat, int *dis){
    for(int i=0;_____(1)_____;i++)
        dis[i]=_____(2)_____;
    for(int i=0;_____(3)_____;i++)
        dis[_____(4)_____]+=_____(5)_____;
}
 
int main(void) {
    int data[N]= {1, 2, 0, 1, 2, 1};
    int dist[V];
    calcDist(_____(6)_____);
    for(int i=0;i<_____(7)_____;i++){
        printf("%d は%d 回",_____(8)_____);
        if(i<_____(9)_____){
            printf(", ");
        }else{
            printf("_____(10)_____");
        }
    }
    /* --- */
    return(0);
}

実行結果：

0 は 1 回, 1 は 3 回, 2 は 2 回出ました.

[2] 次に，calcDist 関数で計算される各値の出現回数が入った配列の先頭要素のアドレスを整数型ポインタ変数 dis で受け取り，その出現回数に比例する確率で $0$ から $V-1$ までの整数値から値を $1$ つ選んで返す関数 getValue を以下の通りに作成し，プログラムの適切な場所に追加した。関数中では，$0$ 以上 $N$ 未満の整数値を等確率で $1$ つ選び，その値から各出現回数を順次減算していき，$0$ を下回ったときの出現回数に対応する値を返している。また，問題 [1] の main 関数中の “/* --- */” を以下の一文と置き換えくじ引きを再現した結果を表示するようにした。空欄を適切に埋めよ。なお，rndInt(x) は $0$ 以上 $x$ 未満の整数値を等確率で $1$ つ選んで返す関数とする。

関数 getValue：

int getValue(int *dis){
    int r= rndInt(N);
    int i;
    for(i=0;i<V;i++){
        r-=_____(1)_____;
        if(_____(2)_____)
            break;
    }
    return(_____(3)_____);
}
 

main 関数中の “/* --- */” と置き換えた一文：

   printf("くじ引きを再現して出た値は%d です．",_____(4)_____);

[3] 加えて，calcDist 関数で計算される各値の出現回数が入った配列の先頭要素のアドレスを整数型ポインタ変数 dis で，$0$ から $V-1$ までの任意の整数値を整数型変数 val で受け取り，ある整数値を返す関数 func を以下の通りに作成した。この関数の返り値は何を示すか，くじ引きの文脈に即して説明せよ。

int func(int *dis, int val){
    if(dis[val]==0)
        return(-1);
 
    if(getValue(dis)==val){
        return(1);
    }else{
        return(func(dis, val) + 1);
    }
}

---

解答：

[1]
(1) $\boxed{\text{i < V}}$
(2) $\boxed{0}$
(3) $\boxed{\text{i < N}}$
(4) $\boxed{\text{dat[i]}}$
(5) $\boxed{1}$
(6) $\boxed{\text{data, dist}}$
(7) $\boxed{\text{V}}$
(8) $\boxed{\text{i, dist[i]}}$
(9) $\boxed{\text{V - 1}}$
(10) $\boxed{\text{出ました.n}}$

[2]
(1) $\boxed{\text{dis[i]}}$
(2) $\boxed{\text{r < 0}}$
(3) $\boxed{\text{i}}$
(4) $\boxed{\text{getValue(dist)}}$

[3]
値 val が出るまでくじを繰り返し引いたときの、くじを引いた合計回数。（ただし、値 val のくじが1つも含まれていない場合は -1 を返す）

---

补充说明：

第一题主要考察数组的遍历与频率统计。首先需要对记录频率的数组 dis 进行初始化，由于可能出现的值域为 $0$ 到 $V-1$，因此循环条件(1)为 i < V，将其全部置为0，即(2)填 0。随后遍历抽取结果数组 dat（长度为 $N$），故(3)填 i < N，通过 dis[dat[i]] 来累加对应值的出现次数，每次加1，所以(4)为 dat[i]，(5)为 1。在主函数中，调用 calcDist 函数需传入存放数据的数组和用于记录结果的数组，(6)填 data, dist。打印时需要遍历所有可能的值（共 $V$ 个），(7)填 V，输出对应的值及其次数，(8)填 i, dist[i]。为了实现格式化输出，前 $V-1$ 个元素用逗号隔开，最后一个元素后加上结束语，因此(9)填 V - 1，(10)填 出ました.\n。

第二题考察根据权重进行随机抽取的算法实现（即轮盘赌算法）。产生一个 $0$ 到 $N-1$ 之间的随机数 r，依次减去各元素对应的频数，即(1)填 dis[i]。题目说明“当降至 $0$ 以下时”停止减法，这表示当前随机数落在该元素的频数区间内，此时应退出循环，故(2)填 r < 0。跳出循环时的索引 i 即为选中的值，(3)填 i。在主程序中为了输出结果，应调用该函数并传入频率数组 dist，因此(4)填 getValue(dist)。

第三题考察递归函数的执行逻辑。函数 func 接收目标抽取值 val，如果 dis[val] == 0，代表无论如何也不可能抽中该值，直接返回 -1。如果调用 getValue 刚好抽中目标值，返回 1 表示抽取了 1 次。否则进入递归，意味着本次未抽中，还需要继续抽，返回结果为接下来的抽取次数加上当前的 1 次。因此，该递归函数模拟了伯努利试验的过程，其返回值表示为了抽中特定值 val 所需的累计抽取次数。