コマ大の問題をプログラムで解こう4問目 – ラマヌジャン –

 
問題:
 
[1],[2],[3],,,,,,[?],,,,[50]
このように端から順に数字が並んでいます。ある数字の右側にある数字を全部足した数と
左側にある数字を全部足した数の値が等しい時、その数字はいくつか答えなさい。
ただし、並んでいる数字は10個以上50個以下とします。
 
(例えば、8まで並んでいる時は「6」が正解)
(1+2+3+4+5=15、7+8=15)
 
 
さて、まずは、例によって例のごとく、自力で解いてみよう。
 
 
– 問題の解法
数字の総数(最後尾の数)をn, ある数字をmとすると、
   {1+(m-1)}(m-1)/2 = {(m+1)+n}(n-m)/2
⇔ m(m-1) = {n+m+1}(n-m)
⇔ 2m2 = n(n+1)                                                –(1)
ここで、n, n+1は一方が奇数、他方が偶数であり、かつ互いに素であるから、
どちらか一方が奇数となる平方数であり、他方が平方数の2倍となることが分かる。
奇数となる平方数は、10 ≦ n ≦ 50の間に、25, 49しか存在しない。
n = 25の場合、
24×25か25×26が考えられるが、
どちらの場合も、上に示した条件に一致しないので不適。
 
n = 49の場合、
48×49か49×50が考えられるが、
48×49のとき、
48 = 2×24であり、平方数の2倍という条件を満たしていない。
49×50のとき、
50 = 2×25であり、条件を満たす。
したがって、式(1)より
 
2m2 = n(n+1)
 
に各値を代入して、
 
49×50 = 2×52x72 = 2(5×7)2 
 
∴m = 35     –(答え)
が求まる。
 
ちなみに友人曰く、正則連分数を使った素晴らしい方法があるらしい
けど、自分はどうやるのか分からないから・・触れないことにする。。
 
 
– プログラムで解いてみる
まあ・・端的に言えば、足し算をするプログラムを組むだけ。
だから、ちょっとだけ凝ったプログラムを書いてみた。
ホントちょっとだけどね…… (。・x・)ゝ
 
 
— Program Source Code —
#include <stdio.h>
 
#define     START    1                  //define the start number
#define     END      50                  //define the end number
 
int addition(int, int);
 
int main(void)
{
    int n, m;
    for(n=START ; n < END ; n++)          //n:全体数, m:該当数
        for(m=START ; m < END ; m++)
            if(n <= m)
                break;
            else
                if(addition(n,m) == addition(m-1, 0))
                    printf("n=%d, m=%dn", n, m);
    return 0;
}
 
int addition(int n, int m)
{
    return (n == m) ? (0) : ( n + addition(n-1,m) );
}
 
 
— END —
 
 
というわけで、23行、空白行抜いたら20行、のプログラム。
 
 
[実行結果]
 
n=8, m=6
n=49, m=35
 
 
今の場合は、STARTをあえて"1"にしてるので、このような結果になってます。
 
ミソは、addition関数。
・・まあ、ミソって言うほどではないかもしれないけどさー(;´・ω・)
 
カテゴリー: 論考 パーマリンク