今年のセンター試験BASIC

 投稿者：山中和義  投稿日：2009年 1月20日(火)10時36分8秒
  ●問題とプログラム

p,qは異なる自然数とする。
与えられた自然数kについて、d以下の自然数kのうちで
　k=m*p+n*q、m,nは０以上の整数
で表すことができるものを小さい順に列挙する。

例. p=3,q=7,d=15のとき、 3  6  7  9  10  12  13  14  15  総数= 9
例. p=3,q=7,d=100のとき、総数= 94。


100 INPUT PROMPT "p=": P
110 INPUT PROMPT "q=": Q
120 INPUT PROMPT "d=": D
130 LET U=0
140 FOR K=1 TO D !d以下の自然数kのうちで
150    IF K-INT(K/P)*P=0 THEN GOTO 210 !kがpの倍数の場合（k=m*p+0）　※MOD(K,P)=0
160    FOR M=0 TO INT(K/P) !０からPで割った商まで　∵k=m*p+r
170       LET R=K-M*P !k-m*p=n*q
180       IF R-INT(R/Q)*Q=0 THEN GOTO 210 !rがqの倍数の場合　※MOD(R,Q)=0
190    NEXT M
200    GOTO 230 !該当なし。次へ
210    PRINT K !条件を満たす
220    LET U=U+1
230 NEXT K
240 PRINT "総数="; U
250 END



●P=3,Q=7,D=100での総数を求める問題の解法について
　トレースするには手順が多すぎる。世界のナベアツではないが、ほとんどアホになってしまう。

そこで、・・・

・拡張ユークリッドの互除法　m*3+n*7=gcd(3,7)=1=k　より
　整数組(m,n)で、kの倍数を表すことができる。（一意ではない）

これより
　問題文にヒントがある。
　1～3*7=21までの整数が表現できるか確認する。　1,2,4,5,8,11が無理。


・「３の倍数と７の倍数との和」の線形性は、「左斜め」になる。（7=2*3+1ずつずれる）

　縦：３の倍数、横：７の倍数
   0   7  14  21  28  35  42  49  56  63  70  77  84
   3  10  17  24  31  38  45  52  59  66  73  80  87
   6  13  20  27  34  41  48  55  62  69  76  83  90
   9  16  23  30  37  44  51  58  65  72  79  86  93
  12  19  26  33  40  47  54  61  68  75  82  89  96
  15  22  29  36  43  50  57  64  71  78  85  92  99
  18  25  32  39  46  53  60  67  74  81  88  95 102
  21  28  35  42  49  56  63  70  77  84  91  98 105
  24  31  38  45  52  59  66  73  80  87  94 101 108
  27  34  41  48  55  62  69  76  83  90  97 104 111
  30  37  44  51  58  65  72  79  86  93 100 107 114
  33  40  47  54  61  68  75  82  89  96 103 110 117
  36  43  50  57  64  71  78  85  92  99 106 113 120
  39  46  53  60  67  74  81  88  95 102 109 116 123
  42  49  56  63  70  77  84  91  98 105 112 119 126
  45  52  59  66  73  80  87  94 101 108 115 122 129

これより
　一目瞭然！？


・・・と考えてみた。 		 

Re: 今年のセンター試験BASIC

 投稿者：山中和義  投稿日：2009年 1月21日(水)11時08分47秒
  > No.249[元記事へ]

●210行目で、条件を満たすMとNを表示するように改良してみた。

・150行目を削除
・210行目にM,Nの計算を追加

100 INPUT PROMPT "p=": P
110 INPUT PROMPT "q=": Q
120 INPUT PROMPT "d=": D
130 LET U=0
140 FOR K=1 TO D !d以下の自然数kのうちで
150    !
160    FOR M=0 TO INT(K/P) !０からKをPで割った商まで
170       LET R=K-M*P !k-m*p=n*q
180       IF R-INT(R/Q)*Q=0 THEN GOTO 210 !rがqの倍数の場合　※MOD(R,Q)=0
190    NEXT M
200    GOTO 230 !該当なし。次へ
210    PRINT K; M;INT(R/Q) !条件を満たすM,N　※
220    LET U=U+1
230 NEXT K
240 PRINT "総数="; U
250 END


＊アルゴリズムの数学的背景
不定方程式 k=m*p+n*q は、k-m*p=n*q と変形される。
合同式で表すと、k-m*p≡0 mod q となる。

m は０以上の整数、p は自然数より、m*p≧0 となる。　同様に、n*q≧0。
また、n*q=k-m*p≧0 より、k≧m*p となる。
したがって解があれば、mは0～INT(K/P)で見つかる。



●(m,n)の組は一通りでない。その組を調べる。

・180行目を変更と追加（210,220行目）
・150,200,210,220行目を削除

100 INPUT PROMPT "p=": P
110 INPUT PROMPT "q=": Q
120 INPUT PROMPT "d=": D
130 LET U=0
140 FOR K=1 TO D !d以下の自然数kのうちで
150    !
160    FOR M=0 TO INT(K/P) !０からKをPで割った商まで
170       LET R=K-M*P !k-m*p=n*q
180       IF R-INT(R/Q)*Q=0 THEN !rがqの倍数の場合　※MOD(R,Q)=0
             PRINT K; M;INT(R/Q) !条件を満たすM,N
             LET U=U+1
          END IF
190    NEXT M
200    !
210    !
220    !
230 NEXT K
240 PRINT "総数="; U !※意味が変わる
250 END
 

戻る