東京大学 情報理工学系研究科 創造情報学専攻 2015年2月実施 プログラミング

标签：

• Tokyo-University
• Linear-Congruential-Generator
• Recursion

Author

itsuitsuki

Description

(1) The following function $f$ is a function often used as a simple random number generator.

$$f(n) = \begin{cases} 1 & \text{if } n < 1, \\ (161 \times f(n-1) + 2457) \mod 2^{24} & \text{otherwise}. \end{cases}$$

where $n$ is a non-negative integer and $mod$ denotes a modulus operator (the remainder). Write a program that computes $f(n)$ for given $n$. Then print the value of $f(100)$ by using this program.

(2) Write a program that counts the number of $i$ such that $i < 100$ and $f(i)$ is an even number.

(3) Write a program that counts the number of $i$ such that $i$ is an odd number, $i < 100$, and $f(i)$ is an even number.

(4) Write a program that prints the value of $f(1000000)$.

(5) Write a program that computes the following function $g$ where $n$ is a non-negative integer:

$$g(n) = \begin{cases} 1 & \text{if } n < 1, \\ (1103515245 \times g(n-1) + 12345) \mod 2^{26} & \text{otherwise}. \end{cases}$$

Then run the program to print the values of $g(2)$ and $g(3)$.

(6) Write a program that computes the smallest positive integer $k$ such that $g(n + k) = g(n)$ for any non-negative integer $n$.

(7) Write a program that computes the smallest positive integer $k$ such that $h(n+k) = h(n)$ for any non-negative integer $n$. Write on the answer sheet why the program correctly computes $k$. $h$ is a function defined as follows:

$$h(n) = g(n) \mod 2^{10}$$

题目描述

1. 对非负整数 (n)，定义常用作简单伪随机数发生器的递推函数 [ f(n)= \begin{cases} 1,&n<1,\ (161f(n-1)+2457)\bmod2^{24},&n\ge1. \end{cases} ] 其中 (\bmod) 表示取余。编写程序计算给定 (n) 的 (f(n))，并输出 (f(100))。
2. 统计满足 (i<100) 且 (f(i)) 为偶数的 (i) 的个数。
3. 统计满足 (i<100)、(i) 为奇数且 (f(i)) 为偶数的 (i) 的个数。
4. 编写程序输出 (f(1000000))。
5. 对非负整数 (n)，定义 [ g(n)= \begin{cases} 1,&n<1,\ (1103515245g(n-1)+12345)\bmod2^{26},&n\ge1. \end{cases} ] 编写程序计算 (g)，并运行输出 (g(2)) 与 (g(3))。
6. 编写程序求最小正整数 (k)，使对任意非负整数 (n) 均有 (g(n+k)=g(n))。
7. 定义 [ h(n)=g(n)\bmod2^{10}. ] 编写程序求使任意非负整数 (n) 均满足 (h(n+k)=h(n)) 的最小正整数 (k)，并在答题纸上说明程序为何能正确求得该 (k)。

考点

• 线性同余发生器：按乘加取模递推生成序列，分析模为 (2) 的幂时序列状态与周期。
• 递归与迭代实现：避免对百万级下标使用深递归，改用迭代并正确控制整数乘法及取模。
• 周期检测：利用有限状态序列或数论性质求 (g) 及其低 10 位投影 (h) 的最小全局周期，并论证算法正确性。