Cygwinでデバッグ/例題2
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[Cygwinでデバッグ/例題2]]
* 三角数の和への分解 [#ha7ce12a]
** 三角数の説明 [#n94a6c7c]
- 三角数とは、正三角形の形に点を並べたときに並ぶ点の数で...
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105,...
~
●
● ●●
● ●● ●●●
● ●● ●●● ●●●●
● ●● ●●● ●●●● ●●●●●
① 1 ② 3 ③ 6 ④ 10 ⑤ 15
~→http://www.geocities.jp/yasuko8787/z094.htm
- n 番目の三角数は次の公式で求められる。→http://kotobank....
n * (n+1) / 2
- どんな自然数も、３つ以下の三角数の和に分解することがで...
例: 9 = 3 + 6
例: 10 = 1 + 3 + 6
例: 18 = 6 + 6 + 6
> 同じ三角数を何度も使って分解してよい。
> この定理はガウスによって証明された。
- このような「和への分解」は、自然数によっては２通り以上...
例: 12 = 6 + 6
12 = 1 + 1 + 10
12 = 3 + 3 + 6
** 作りたいプログラム [#i92b803a]
自然数のうちで、三角数の和に分解したときに、なるべく分解...
以下の指示に従って、順にプログラムを作れ。
~
- (1) n 番目の三角数を計算する関数
int tri(int n)
を作りなさい。main() 関数は、
int main(void)
{
int i;
for (i=1; i<10; i++) {
printf("tri(%d) = %d\n", i, tri(i));
}
return 0;
}
などとして、動作を確認せよ。
~
- (2) 自然数 p が与えられたときに、''ちょうど３つ''の三角...
void sum_of_tri(int p)
を作りなさい。分解のしかたは、自由に決めてよい。少なくと...
main() 関数は、
int main(void)
{
sum_of_tri(10);
sum_of_tri(12);
return 0;
}
などとして、動作を確認せよ。
> ２つの三角数の和に分解することは、まだ考えなくてよい。...
> ヒント
for (....) {
for (....) {
for (....) {
sum = tri(i) + tri(j) + tri(k);
if (sum == p) {
~
- (3) 自然数 p が与えられたときに、次のような動作をする関数
int num_of_sum_of_tri(int p)
を作りなさい。
-- p を''３つ以下''の三角数の和に分解する。
-- 分解のバリエーションをすべて調べあげる。
-- 関数の戻り値としては、その分解の種類（バリエーション）...
-- 具体的な分解のしかたは（関数の戻り値としては）返さなく...
> ヒント１：「３つ以下」の部分を、「ちょうど３つ、ただし0...
例: 6 = 0 + 0 + 6
6 = 0 + 3 + 3
> ヒント２：重複する分解は、ループの順序を工夫することで...
例: 10 = 1 + 3 + 6 で１通りと数えるとすると、
10 = 1 + 6 + 3 や、
10 = 3 + 1 + 6 などは、探索しないように工夫すればよ...
~
- (4) 1000 未満の自然数で、分解の種類がもっとも多いものを...
(3) で作った関数を繰り返し呼び出すことで実現できるはずで...
出力例: 12 は 3 通りに分解できます。
> num_of_sum_of_tri() 関数が、画面表示をしていると、時間...
~
- (5) 同様に 10000 未満の自然数について調べよ。数秒で結果...
> num_of_sum_of_tri() 関数での探索に、無駄がないか検討せ...
> なお、gcc でのコンパイル時にオプションをつけると、同じ...
gcc -O2 hoge.c
のように、"-O2"（マイナス・大文字オー・に）を付け加えると...
~
- (6) 同様に 100000 未満の自然数について調べよ。数秒で結...
無駄な計算を繰り返していないか、あるいはアルゴリズムやデ...
> Cygwin 環境で実行時間を測るには、
./a.exe
を実行する代わりに、
time ./a.exe
と、先頭に "time" を付けて実行すればよい。出力例は以下の...
real 0m0.020s
user 0m0.008s
sys 0m0.004s
real の欄はバックグラウンドで動くプログラムの影響を受けて...
** 解答の一部 [#i5b1054a]
- (3) 例えば 30 ならば次の４通りに分解される。
30 = 0 + 15 + 15
30 = 1 + 1 + 28
30 = 3 + 6 + 21
30 = 10 + 10 + 10
- (4)
9?2 は 2? 通りに分解できます。
- (5)
9??6 は 8? 通りに分解できます。
- (6)
9??92 は 3?3 通りに分解できます。
（注意）? は伏字である。実際には数字１桁（０から９のどれ...
終了行:
[[Cygwinでデバッグ/例題2]]
* 三角数の和への分解 [#ha7ce12a]
** 三角数の説明 [#n94a6c7c]
- 三角数とは、正三角形の形に点を並べたときに並ぶ点の数で...
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105,...
~
●
● ●●
● ●● ●●●
● ●● ●●● ●●●●
● ●● ●●● ●●●● ●●●●●
① 1 ② 3 ③ 6 ④ 10 ⑤ 15
~→http://www.geocities.jp/yasuko8787/z094.htm
- n 番目の三角数は次の公式で求められる。→http://kotobank....
n * (n+1) / 2
- どんな自然数も、３つ以下の三角数の和に分解することがで...
例: 9 = 3 + 6
例: 10 = 1 + 3 + 6
例: 18 = 6 + 6 + 6
> 同じ三角数を何度も使って分解してよい。
> この定理はガウスによって証明された。
- このような「和への分解」は、自然数によっては２通り以上...
例: 12 = 6 + 6
12 = 1 + 1 + 10
12 = 3 + 3 + 6
** 作りたいプログラム [#i92b803a]
自然数のうちで、三角数の和に分解したときに、なるべく分解...
以下の指示に従って、順にプログラムを作れ。
~
- (1) n 番目の三角数を計算する関数
int tri(int n)
を作りなさい。main() 関数は、
int main(void)
{
int i;
for (i=1; i<10; i++) {
printf("tri(%d) = %d\n", i, tri(i));
}
return 0;
}
などとして、動作を確認せよ。
~
- (2) 自然数 p が与えられたときに、''ちょうど３つ''の三角...
void sum_of_tri(int p)
を作りなさい。分解のしかたは、自由に決めてよい。少なくと...
main() 関数は、
int main(void)
{
sum_of_tri(10);
sum_of_tri(12);
return 0;
}
などとして、動作を確認せよ。
> ２つの三角数の和に分解することは、まだ考えなくてよい。...
> ヒント
for (....) {
for (....) {
for (....) {
sum = tri(i) + tri(j) + tri(k);
if (sum == p) {
~
- (3) 自然数 p が与えられたときに、次のような動作をする関数
int num_of_sum_of_tri(int p)
を作りなさい。
-- p を''３つ以下''の三角数の和に分解する。
-- 分解のバリエーションをすべて調べあげる。
-- 関数の戻り値としては、その分解の種類（バリエーション）...
-- 具体的な分解のしかたは（関数の戻り値としては）返さなく...
> ヒント１：「３つ以下」の部分を、「ちょうど３つ、ただし0...
例: 6 = 0 + 0 + 6
6 = 0 + 3 + 3
> ヒント２：重複する分解は、ループの順序を工夫することで...
例: 10 = 1 + 3 + 6 で１通りと数えるとすると、
10 = 1 + 6 + 3 や、
10 = 3 + 1 + 6 などは、探索しないように工夫すればよ...
~
- (4) 1000 未満の自然数で、分解の種類がもっとも多いものを...
(3) で作った関数を繰り返し呼び出すことで実現できるはずで...
出力例: 12 は 3 通りに分解できます。
> num_of_sum_of_tri() 関数が、画面表示をしていると、時間...
~
- (5) 同様に 10000 未満の自然数について調べよ。数秒で結果...
> num_of_sum_of_tri() 関数での探索に、無駄がないか検討せ...
> なお、gcc でのコンパイル時にオプションをつけると、同じ...
gcc -O2 hoge.c
のように、"-O2"（マイナス・大文字オー・に）を付け加えると...
~
- (6) 同様に 100000 未満の自然数について調べよ。数秒で結...
無駄な計算を繰り返していないか、あるいはアルゴリズムやデ...
> Cygwin 環境で実行時間を測るには、
./a.exe
を実行する代わりに、
time ./a.exe
と、先頭に "time" を付けて実行すればよい。出力例は以下の...
real 0m0.020s
user 0m0.008s
sys 0m0.004s
real の欄はバックグラウンドで動くプログラムの影響を受けて...
** 解答の一部 [#i5b1054a]
- (3) 例えば 30 ならば次の４通りに分解される。
30 = 0 + 15 + 15
30 = 1 + 1 + 28
30 = 3 + 6 + 21
30 = 10 + 10 + 10
- (4)
9?2 は 2? 通りに分解できます。
- (5)
9??6 は 8? 通りに分解できます。
- (6)
9??92 は 3?3 通りに分解できます。
（注意）? は伏字である。実際には数字１桁（０から９のどれ...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
