javaのプログラミング（連続する整数の和）

javaのプログラミング（連続する整数の和）

大学で出た課題です。
「ある自然数nを入力し、n=○+○+…+○と連続する整数の和で表すプログラミングをつくれ。」というものです。
以下に、私が考えたものを載せます。これだと連続する2つの整数の和では表すことができるのですが、3つ以上の整数の和を表すことができません。どうすればよいでしょうか？

import java.io.*;
public class 　n {
public static void main(String[] args) {
int n;

BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
try{
String line;
System.out.print("整数：");
line = rd.readLine();
n = Integer.parseInt(line);
}
catch(IOException e){
System.out.println("入力エラーが発生しました。");
return;
}
catch(NumberFormatException e){
System.out.println("整数を入力してください。");
return;
}

for(int i=1;i<=n;i++){
int k=i+1;
if(i+k==n)
System.out.println(i+"+"+k);
}
}
}

No.2 回答者： nag0720 回答日時： 2010/07/27 07:35

javaの質問ですが数学カテなので数学的に考察してみます。

もしnが3の倍数なら、例えばn=12の場合はn=4*3なので、
nは4を真ん中にした3個の数の合計となります。（n=3+4+5）
もしnが5の倍数なら、例えばn=20の場合はn=4*5なので、
nは4を真ん中にした5個の数の合計となります。（n=2+3+4+5+6）

つまり、nが奇数の倍数なら、n=m*(2k+1)とするとき、
nはmを真ん中にした(2k+1)個の数の合計になります。
n=(m-k)+(m-k+1)+・・・+(m-1)+m+(m+1)+(m+2)+・・・+(m+k)

ただし、k≧mのときは(m-k)は負数になりますが、
m＞0なので必ず(m-k)と相殺できる正数(k-m)の項が存在するので、
n=(k-m+1)+(k-m+2)+・・・+(m+k)
となります。（項数は2m個）


例．n=90=2*3*3*5 の場合
3の倍数とみたとき、m=30,k=1
n=29+30+31
5の倍数とみたとき、m=18,k=2
n=16+17+18+19+20
9の倍数とみたとき、m=10,k=4
n=6+7+8+9+10+11+12+13+14
15の倍数とみたとき、m=6,k=7
n=2+3+4+5+6+7+8+9+10+11+12+13
45の倍数とみたとき、m=2,k=22
n=21+22+23+24


n=2^mとなる場合は、nを連続する２個以上の整数の和で表すことはできません。


javaのコーディング方法について知りたいなら、プログラミングのカテゴリーで質問してみてください。

No.1 回答者： x1yobigun 回答日時： 2010/07/26 23:25

エラトステネスの篩を、順次総なめにしているみたいな感じのアルゴリズムですね。

力任せにコーディングする前に分析しましょう。

n : 自然数
m : 整数（マイナス、０もOK)　と考えて

連続２整数の和で表す方法
自然数 n が奇数のとき、つまり n=2m+1 =>　n=m+(m+1)
自然数 n が偶数のとき、つまり n=2m => （不可能）
　なぜなら、連続２整数は、かならず奇数、偶数のペアであり、
　和は必ず奇数になるから。

連続３整数の和で表す方法
整数 n が３の倍数のとき、つまり　n=3m => (m-1) + m + (m+1)
整数 n が３を法として１になるとき、つまり n=3m+1 => （不可能）
整数 n が３を法として２になるとき、つまり n=3m+2 => （不可能）
　なぜなら、連続３整数の和は、必ず３の倍数になるから。
　（連続３整数の１つは必ず３の倍数、他は３を法として１、２になる
　　整数であるから。これで分かんないなら、力ずくで３パターン計算
　　して証明してもよい。）
　　3m + (3m+1) + (3m+2) = 9m+3 = 3(3m+1)
(3m-1) + 3m + (3m+1) = 9m = 3(3m)
(3m-2) + (3m-1) + 3m = 9m-3 = 3(3m-1)

・・・

連続N整数の和で表す方法

★再帰的呼び出しを使ってはどうでしょうか。