-PR-
解決
済み

課題;素因数分解

  • すぐに回答を!
  • 質問No.88621
  • 閲覧数766
  • ありがとう数0
  • 気になる数0
  • 回答数8
  • コメント数0

お礼率 15% (2/13)

1)和が一定(ここでは4)となる自然数の列を全て列挙するプログラムを教え
てください。
2)再帰を用いずに素因数分解を行うプログラムを教えてくさい。
3)再帰を用いたプログラムと、再帰を用いないプログラムの比較・検討を行っ
てください。
通報する
  • 回答数8
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.8
レベル14

ベストアンサー率 50% (1122/2211)

> ここで、今日ヒントが出たのですが、次のプログラムを参考にして(1)をやってくださいとのことでした。

なんてぇ補足 (^^;
要するに、再帰を使え、とのことかな?

#include <iostream.h>

void sum(int x, int xx[], int n)
{
  int i, s;
  for (i = 0, s = 0 ; i < n ; ++i)
    s += xx[i];
  if (s == x) {
    for (i = 0 ; i < n ; ++i)
      cout << " " << xx[i];
    cout << endl;
    return;
  }
  for (i = 1 ; i <= x - s ; ++i) {
    xx[n] = i;
    sum(x, xx, n + 1);
  }
}

int main()
{
  int x;
  cout << "sum:";
  cin >> x;

  int xx[10];
  sum(x, xx, 0);

  return 0;
}

たいして分かり易くなったわけではありませんね。

■以下、余談

honiyon> 学校の課題ですよね?これ
honiyon> 他力本願な姿勢であると誤解されてしまいますよ

最初から、質問のタイトルに「課題」と入っているのだし、
質問サイトの本質は、他社の知恵におすがりしよう、というのだから
自分で何をしていようがかまわんとは思います。ただ、

> スマソ。

2ch なんか見ている暇があったら、テキストや参考書を開きましょう :-)
とは言うものの、あのソースを参考に、っていうのも辛いものが
ありますね。

念の為、最後に書いておきますけど、私が提示しているソースは
全部 c++ なので、多分、そのまま課題には使えないと思いますよ。
-PR-
-PR-

その他の回答 (全7件)

  • 回答No.2
レベル14

ベストアンサー率 50% (1122/2211)

1)は、つまらないのでパス。 2)は、こんな感じ(効率は、あまり良くないけど)。 #include <iostream.h> int main() {   int i = 2, x;   cout << "input n:";   cin >> x;   while (i <= x) {     if ((x % ...続きを読む
1)は、つまらないのでパス。

2)は、こんな感じ(効率は、あまり良くないけど)。

#include <iostream.h>

int main()
{
  int i = 2, x;
  cout << "input n:";
  cin >> x;
  while (i <= x) {
    if ((x % i) == 0) {
      cout << " " << i;
      x /= i;
    } else {
      ++i;
    }
  }
  cout << endl;

  return 0;
}

3)の前に、再帰版のプログラムはこんな感じ。

include <iostream.h>

void pri(int x, int i)
{
  if (x <= 1) return;
  if ((x % i) == 0) {
    cout << " " << i;
    pri(x / i, i);
  } else {
    pri(x, i+1);
  }
  return;
}

int main()
{
  int x;
  cout << "input n:";
  cin >> x;
  pri(x, 2);
  cout << endl;

  return 0;
}

はっきり言って、(この程度のプログラムでは)たいした違いはない、よね。

再帰を使ったからといって、ロジックの見通しが良くなっているわけでも
無いし、却ってメモリ(スタック)を無駄に食うだけ。

あくまでもソフト屋さんの視点での比較なので、学校のレポートで点数を
もらえる保証は無いよ ;-)

# と言う意味では、「自信あり」とするわけにはいかないか…


  • 回答No.1
レベル13

ベストアンサー率 37% (331/872)

こんにちは、honiyonです。    どの辺が分からないのですか?  プログラミングなのか、コーディングなのか。 ナドナド。  また、3番に関しては他人に検討を依頼するならば、まずは自分の意見を記述し、「皆さんはどう思いますか?」を問いかけるのが筋だと思います。
こんにちは、honiyonです。
 
 どの辺が分からないのですか?
 プログラミングなのか、コーディングなのか。 ナドナド。
 また、3番に関しては他人に検討を依頼するならば、まずは自分の意見を記述し、「皆さんはどう思いますか?」を問いかけるのが筋だと思います。
  • 回答No.3
レベル10

ベストアンサー率 18% (35/185)

あんたもしかしてとーこーだいせい? 今日のドイツ語の授業中にそんな話してるやつらがいて・・・・・ 横でそいつらの話聞いててぷっってわらってしまった・・・・ 1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば いいでしょ? #define kokodeha 4 //(笑) for (int i=0;i<kokodeha;i++){ cout << i ...続きを読む
あんたもしかしてとーこーだいせい?
今日のドイツ語の授業中にそんな話してるやつらがいて・・・・・
横でそいつらの話聞いててぷっってわらってしまった・・・・

1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば
いいでしょ?
#define kokodeha 4 //(笑)
for (int i=0;i<kokodeha;i++){
cout << i<<","<<kokodea-i<<endl;
}
2はwebで検索かけても、図書館に行ってもあるので省略(下にもあるし)

3)
再帰を用いるとスタックを食う(レポートに書くときは何に比例してって
書かないと点数がこないかも)
んで計算量はそんなには変わらないよね
  • 回答No.4
レベル14

ベストアンサー率 50% (1122/2211)

> 1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば > いいでしょ? 「ぷっ」 1、2、1 や 1、1、1、1 も「和が一定(ここでは4)となる自然数の列」 なのよ。君もちゃんと授業に集中しなさいね :-) どうせ、力ずくで求める解(ループが四重になっている奴)を書いてくるのが いるだろうと思ってたのだけどなあ。
> 1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば
> いいでしょ?

「ぷっ」

1、2、1 や 1、1、1、1 も「和が一定(ここでは4)となる自然数の列」
なのよ。君もちゃんと授業に集中しなさいね :-)

どうせ、力ずくで求める解(ループが四重になっている奴)を書いてくるのが
いるだろうと思ってたのだけどなあ。
  • 回答No.6
レベル13

ベストアンサー率 37% (331/872)

 自分で考えてますか? 学校の課題ですよね?これ。  質問内容や、補足内容には「こういう問題が出されました」「こう指示されました」とだけ書かれており、ご自分でなされた努力や考えなどが一切出されていません。  これでは、ただ出された問題を他人に解いてもらおうとしてる、他力本願な姿勢であると誤解されてしまいますよ。 ...続きを読む
 自分で考えてますか? 学校の課題ですよね?これ。
 質問内容や、補足内容には「こういう問題が出されました」「こう指示されました」とだけ書かれており、ご自分でなされた努力や考えなどが一切出されていません。

 これでは、ただ出された問題を他人に解いてもらおうとしてる、他力本願な姿勢であると誤解されてしまいますよ。
補足コメント
yoshi-nao

お礼率 15% (2/13)

スマソ。
ひたすら考えてるんですがまったくわからないのです。。。
誰に聞いても教えていただけないので。
投稿日時 - 2001-06-12 16:39:42
  • 回答No.5
レベル14

ベストアンサー率 50% (1122/2211)

試しに力ずくで求めるプログラムを書いてみたら、重大な欠点(後述)が あって、却って簡単にならないのね。 というわけで、1)もやってみました。 #include <iostream.h> int main() {   int x, n;   cout << "sum:";   cin >> x;   n = 1 < ...続きを読む
試しに力ずくで求めるプログラムを書いてみたら、重大な欠点(後述)が
あって、却って簡単にならないのね。

というわけで、1)もやってみました。

#include <iostream.h>

int main()
{
  int x, n;

  cout << "sum:";
  cin >> x;
  n = 1 << (x-1);
  for (int i = 0 ; i < n ; ++i) {
    for (int j = 0, a = 1 ; j < x ; ++j) {
      if ((1 << j) & i) {
        ++a;
      } else {
        cout << " " << a;
        a = 1;
      }
    }
    cout << endl;
  }

  return 0;
}

「和」を指定できるように作ってみた(31までだけど)。4を指定した
ときの出力は

% wa
sum:4
1 1 1 1
2 1 1
1 2 1
3 1
1 1 2
2 2
1 3
4

って感じ。ソースだけ読んでも理屈が分からないと思うので、ちょっと
解説を。

例えば、和が4のときの自然数の列は、全て、1を基準に考えられる。
図示してみると、
1 2 1 → 1 1+1 1
3 1   → 1+1+1 1
という感じ。

つまり、4つ並んだ1のそれぞれの隙間を+で表現して、ひとつの数値と
見るか、空白で区切って別の数値としてみるか。

先に提示したプログラムでは、その隙間をビット表現として1ならば
+、0ならば空白だと思って、隙間の組み合わせ(4なら2の3乗)だけ
繰り返してみています。

# 下手な説明だなあ (^^;


ちなみに、「力ずくで書けるから」と思っていたプログラムは、

#include <iostream.h>

int main()
{
  int i,j,k,l;
  for (i = 0 ; i <= 4 ; ++i)
    for (j = 0 ; j <= 4 ; ++j)
      for (k = 0 ; k <= 4 ; ++k)
        for (l = 0 ; l <= 4 ; ++l)
          if (i + j + k + l == 4) {
            if (i != 0) cout << " " << i;
            if (j != 0) cout << " " << j;
            if (k != 0) cout << " " << k;
            if (l != 0) cout << " " << l;
            cout << endl;
          }
  return 0;
}

という感じのプログラム。動かしてみると分かるのだけれど、
組合わせのダブりが出てくるのだよね。例えば、1・1・2だけ
でも4回も出てくる。

ダブりをはじくように考えると、却って面倒なので、考え方から
見直してみたのが、最初に出したプログラムなの。
補足コメント
yoshi-nao

お礼率 15% (2/13)

ここで、今日ヒントが出たのですが、次のプログラムを参考にして(1)をやってく
ださいとのことでした。

例)和がw以下となる長さnの数列をすべて表示するためのプログラム

#include<stdio.h>

void abs_sum( int n, int w);
int main()
{
int w =2,n =3;
abs_sum( n, w);
return 0;
}
void abs_sum( int n, int w)
{
void in_abs_sum( int total_length, int n, int w);
in_abs_sum( n,0,w);
}
void in_abs_sum( int total_length, int pos, int w)
{
int i, j, called =0;
if ( pos >= total_length ){
putchar( '\n');
return;
}
for ( i =0;i <= w;++i){
if ( called++ ){
for ( j =0;j < pos;++j){
printf(" ");
}
}
printf("%2d",i);

in_abs_sum( total_length, pos +1,w-i);
}
}

出力したらこうなりました。
0 0 0
1
2
1 0
1
2 0
1 0 0
1
1 0
2 0 0
Press any key to continue
投稿日時 - 2001-06-12 15:55:48
  • 回答No.7
レベル10

ベストアンサー率 18% (35/185)

どうでもいいけど・・・ 問題読み間違えました(^^;ご指摘ど~も
どうでもいいけど・・・
問題読み間違えました(^^;ご指摘ど~も
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ