ｾﾝﾀｰ試験: 数学IIBのﾌﾟﾛｸﾞﾗﾑについて語るｽﾚ part3 [sc] | レス11-61

37 2014/01/24(金) 11:54:21.15: 2014年度数学IIB 第6問

2 以上の自然数 N に対して、 1 から N までの自然数の積

N! = 1 x 2 x ... x N

の素因数分解を考える。

(1)
N = 6 のとき、 N! の素因数分解は 6! = 2^[ア] x 3^[イ] x 5 である。
6! は、素因数 2 を [ア] 個、素因数 3 を [イ] 個、素因数 5 を 1 個もつ。

ここまで見た

38 2014/01/24(金) 12:13:02.79: (2)
N! がもつ素因数 2 の個数を求める方法について考えよう。
まず、 N/2 の整数部分を M とおく。 N 以下の自然数の中には、
M 個の偶数 2, 4, ..., 2M がある。その他の奇数の積を Q とおくと、
N! は次のように表すことができる。

N! = Q x 2 x 4 x ... x 2M = Q x 2^M x M!

したがって、 N! は少なくとも M 個の素因数 2 をもつことがわかる。
さらに、 M! がもつ素因数 2 の個数を求めるために、 N! に対する手順を
M! に対して再び用いることができる。

つまり、 N! がもつ素因数 2 の個数を求めるためには、 N から N/2 の整数部分
である M を求め、 M を改めて N と考えて、同じ手順を用いて新しく M を求める、
という手順の繰り返しを M < 2 となるまで行えばよい。この手順の繰り返しで
求められたすべての M の和が、 N! がもつ素因数 2 の個数である。

たとえば、 N = 13 の場合には、 13/2 = 6.5 であるから、 M = 6 となる。
この手順を繰り返して M を求めた結果は、 N から M を求める手順を
矢印 ( -> ) で表すと、次のようにまとめられる。

13 -> 6 -> 3 -> 1

太字で表された 6, 3, 1 が、この手順を繰り返して求められた M の値である。
それらの和 6 + 3 + 1 = 10 が、 13! のもつ素因数 2 の個数である。

この手順にしたがって、 2 以上の自然数 N を入力して、 N! がもつ素因数 2 の
個数を出力する ( プログラム1 ) を作成した。
ただし、 INT(X) は X を超えない最大の整数を表す関数である。

ここまで見た

39 2014/01/24(金) 12:33:22.24: ( プログラム1 )

100 INPUT PROMPT "N=" : N
110 LET D = 2
120 LET C = 0
130 LET M = N
140 FOR J = 1 TO N
150 LET M = INT(M/D)
160 LET [ウ]
170 IF [エ] THEN GOTO 190
180 NEXT J
190 PRINT "素因数"; D ; "は"; C ; "個"
200 END

( プログラム1 ) の [ウ] に当てはまるものを、次の (0) 〜 (3) のうちから
一つ選べ。

(0) C = C + 1 (1) C = M (2) C = C + M (3) C = C + M + 1

[エ] に当てはまるものを、次の (0) 〜 (4) のうちから一つ選べ。

(0) M >= D (1) M = D (2) M <= D (3) M < D (4) M > D

( プログラム1 ) を実行し、変数 N に 101 を入力する。
170 行の「 GOTO 190 」が実行されるときの変数 J の値は [オ] である。
また、 190 行で出力される変数 C の値は [カキ] である。

ここまで見た

40 2014/01/24(金) 12:49:39.44: (3)
N! がもつ素因数 2 の個数を求める方法は、他の素因数の個数についても
同様に適用できる。たとえば、 N! がもつ素因数 5 の個数を求める場合は、
まず、 N/5 の整数部分を M とおく。 N 以下の自然数の中には M 個の
5 の倍数があるので、 N! は少なくとも M 個の素因数 5 をもつ。
また、これらの M 個の 5 の倍数を 5 で割った商は 1, 2, ..., M である。
M! の中の素因数 5 の個数を求めるためには、 M を N と考えて、
同じ手順を繰り返せばよい。

したがって、 N! がもつ素因数 5 の個数を求めるためには、 ( プログラム1 ) の
[クケコ] 行を [サ] に変更すればよい。 [サ] に当てはまるものを、
次の (0) 〜 (5) のうちから一つ選べ。

(0) INPUT PROMPT "N=" : N
(1) INPUT PROMPT "C=" : C
(2) INPUT PROMPT "M=" : M
(3) LET C = 5
(4) LET D = 5
(5) LET M = D

変更した ( プログラム1 ) を実行することにより、 2014! は素因数 5 を
[シスセ] 個もつことがわかる。したがって、 2014! がもつ素因数 2 の個数と
素因数 5 の個数について考えることにより、 2014! を 10 で割り切れる限り
割り続けると、 [ソタチ] 回割れることがわかる。

ここまで見た

41 2014/01/24(金) 13:01:21.79: (4)
N 以下のすべての素数が、 N! の素因数として含まれる。その個数は、
素数 2 や素数 5 の場合と同様に求められる。 N 以下のすべての素因数について、
N! がもつ素因数とその個数を順に出力するように、 ( プログラム1 ) を変更して
( プログラム2 ) を作成した。行番号に下線が引かれた行は、変更または追加された
行である。

ただし、繰り返し処理「 FOR K = A TO B 〜 NEXT K 」において、
A が B より大きい場合、この繰り返し処理は実行されず次の処理に進む。

( プログラム2 )

100 INPUT PROMPT "N=" : N
110 FOR D = 2 TO N
111 FOR K = 2 TO D - 1
112 IF [ツ] THEN [テ]
113 NEXT K
120 LET C = 0
130 LET M = N
140 FOR J = 1 TO N
150 LET M = INT(M/D)
160 LET [ウ]
170 IF [エ] THEN GOTO 190
180 NEXT J
190 PRINT "素因数"; D ; "は"; C ; "個"
191 NEXT D
200 END

ここまで見た

42 2014/01/24(金) 13:09:21.02: ( プログラム2 ) の 111 行から 113 行までの処理は、 D が素数であるかどうかを
判定するためのものである。 [ツ] 、 [テ] に当てはまるものを、
次の (0) 〜 (8) のうちから一つずつ選べ。ただし、同じものを選んでもよい。

(0) INT(D/K) = 1
(1) INT(D/K) > 1
(2) D = INT(D/K) * K
(3) D <> INT(D/K) * K
(4) GOTO 120
(5) GOTO 130
(6) GOTO 180
(7) GOTO 190
(8) GOTO 191

( プログラム2 ) を実行し、変数 N に 26 を入力したとき、 190 行は [ト] 回
実行される。 [ト] 回のうち、変数 C の値が 2 となるのは [ナ] 回である。

ここまで見た

43 2014/01/24(金) 16:20:41.21: ループを何回実行するかは意識するけど、
C == 2 になるのが何回か？
とかまであんまり意識しないから、違和感あるな。
如何にも無理やりな試験問題な感じ。

ここまで見た

44 2014/01/24(金) 16:42:56.25: いや
そこは大事だろ

ここまで見た

45 2014/01/24(金) 17:57:53.91: むしろ大学の研究室で求められてる人材は
いまだにFORTRANだよ
だからとりあえずBASICでよろしい
ということになる

ここまで見た

46 2014/01/24(金) 21:39:31.77: じゃあFORTRANやらせろよ

ここまで見た

47 2014/01/25(土) 04:03:37.59: 高校でプログラムの授業するとき
BASICの実行環境は何を用意してるんだろ
紙の上だけでやってるの？

ここまで見た

48 2014/01/25(土) 13:20:48.88: 教育機関にはMSがVS配ってなかったか

ここまで見た

49 2014/01/25(土) 16:30:33.10: 試験中は手元に実行環境無いんだから、紙の上で考えることに慣れておくべきだよ。

ここまで見た

50 2014/01/27(月) 11:30:36.08: 整数のオーバーフローとか考慮しなくて良いのかな？
特に2014!とか求めさせてるところが気になる

ここまで見た

51 2014/01/27(月) 13:38:01.14: あほハケーン

ここまで見た

52 2014/01/27(月) 17:17:57.77: >27
行番号付けないと問題が成り立たないな。
察してやれ。

ここまで見た

53 2014/01/28(火) 08:57:24.03: ageてる馬鹿はなんなの？

ここまで見た

54 2014/01/28(火) 12:39:59.81: 数学オリンピックの過去問に似た問題があった気がします。
2000!の最後に0は何個並ぶか、見たいな感じのが。

ここまで見た

55 2014/01/28(火) 13:01:01.40: >>54
10 の N 乗 ( N は自然数 ) は 200! を割り切る
このような N の最大値を求めよ

とか

1 から 2014 までを掛けると右端から 0 がいくつ並ぶか

どっかの女子中の入試問題だった希ガス

ここまで見た

56 2014/01/28(火) 13:06:29.35: >>50
Ruby はオーバーフローしないから最適だね！

ここまで見た

57 2014/01/28(火) 17:45:56.13: >>19
http://sci.tea-nifty.com/blog/2014/01/26iib6basickeis.html

ここまで見た

58 2014/01/28(火) 17:55:06.74: >>49
パンチカードの時代のひとですね判ります

ここまで見た

59 2014/01/28(火) 17:57:14.62: >>52
どうみても行番号は悪習
百害あって一利なし

どうせなら >>46 さんも言ってるように
最初から FORTRAN で出題するべき

ここまで見た

60 2014/01/28(火) 18:34:56.45: Dで書いてみた。

import std.conv;
import std.stdio;

int getint(int m)
{
　int n = 0;
　while(n < m){
　　write("N = ? ");
　　try{
　　　readf("%d", &n);
　　　if(n < m) writefln("must be greater than or equal to %d", m);
　　}catch(ConvException){
　　　writeln("must be integer");
　　　n = 0;
　　}
　　readln(); // flush line buffer
　}
　return n;
}

bool isprime(int n)
{
　for(int k = 2; k < n; ++k){
　　int d = n / k;
　　if(d * k == n) return false;
　}
　return true;
}

ここまで見た

61 2014/01/28(火) 18:35:55.42

int main(string[] args)
{
　int n = getint(2);
　writefln("N = %d", n);
　for(int d = 2; d <= n; ++d){
　　if(!isprime(d)) continue;
　　int c = 0, m = n;
　　for(int j = 1; j <= n; ++j){
　　　m /= d;
　　　c += m;
　　　if(m < d) break;
　　}
　　writefln("(D, C) = (%6d, %6d)", d, c);
　}
　return 0;
}