1)和が一定(ここでは4)となる自然数の列を全て列挙するプログラムを教え
てください。
2)再帰を用いずに素因数分解を行うプログラムを教えてくさい。
3)再帰を用いたプログラムと、再帰を用いないプログラムの比較・検討を行っ
てください。

このQ&Aに関連する最新のQ&A

A 回答 (8件)

> ここで、今日ヒントが出たのですが、次のプログラムを参考にして(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++ なので、多分、そのまま課題には使えないと思いますよ。
    • good
    • 0

どうでもいいけど・・・


問題読み間違えました(^^;ご指摘ど~も
    • good
    • 0

 自分で考えてますか? 学校の課題ですよね?これ。


 質問内容や、補足内容には「こういう問題が出されました」「こう指示されました」とだけ書かれており、ご自分でなされた努力や考えなどが一切出されていません。

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

この回答への補足

スマソ。
ひたすら考えてるんですがまったくわからないのです。。。
誰に聞いても教えていただけないので。

補足日時:2001/06/12 16:39
    • good
    • 0

試しに力ずくで求めるプログラムを書いてみたら、重大な欠点(後述)が


あって、却って簡単にならないのね。

というわけで、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回も出てくる。

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

この回答への補足

ここで、今日ヒントが出たのですが、次のプログラムを参考にして(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
    • good
    • 0

> 1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば


> いいでしょ?

「ぷっ」

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

どうせ、力ずくで求める解(ループが四重になっている奴)を書いてくるのが
いるだろうと思ってたのだけどなあ。
    • good
    • 0

あんたもしかしてとーこーだいせい?


今日のドイツ語の授業中にそんな話してるやつらがいて・・・・・
横でそいつらの話聞いててぷっってわらってしまった・・・・

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

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

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;
}

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

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

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

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

こんにちは、honiyonです。


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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q素因数分解をこの問題でどう使うのか??

問題
「a、b、cは自然数とする。
2^3a×3^2b×5^cで表せる6桁の数があり、その中央の4桁は0736であることがわかっているとき、a,b,cの値を求めよ。」

これは中学生の問題です。私は家庭教師をしているのですが、情けないことにこの問題がわかりません。この問題のテーマは「素因数分解の利用」ということなのですが、どう素因数分解を利用するのかわかりません。

~私の解法(素因数分解の利用なし)~
3^2b=9の倍数なので、9の倍数の性質と2×5=10を利用して6桁の数が「207360」とわかったのですが、素因数分解を利用していないので、この解法ではないと思います。そもそも9の倍数の性質を知らないと解けない問題自体見たことがありません。

素因数分解を利用する解法がわかる方はぜひ教えて下さい。お願いします。

Aベストアンサー

  2^(3a)*3^(2b)*5^c = d * 10^5 + 736 * 10 + e
とおくと,
  736 * 10 = 2^6 * 5 * 23
また,左辺は,
  2^(3(a-1)) * 3^(2(b-1)) * 5^(c-1) * 2^3 * 3^2 * 5
a ≧ 1 , b ≧ 1 , c ≧ 1 より,a-1 ≧ 0 , b-1 ≧ 0 , c-1 ≧ 0 より,
  e = 0
∴2^(3(a-1))*3^(2(b-1))*5^(c-1) * 2^3*3^2*5
 = d * 10^5 + 2^6 * 5 * 23
 = 2^6 * 5 * ((625/2)*d + 23)  ← 2^5でくくるべきだが,3a乗よりOK
したがって,d は2の倍数である.d = 2 , 4 , 6 , 8 を代入して,9の倍数になるのは
  d = 2
のときだけであり,このとき,((625/2)*d + 23) = 648 = 3^4 * 2^3
よって,a = 3 , b = 2 , c = 1

素因数分解をメインに使ってみましたが,9の倍数の性質を使いたいですね.

  2^(3a)*3^(2b)*5^c = d * 10^5 + 736 * 10 + e
とおくと,
  736 * 10 = 2^6 * 5 * 23
また,左辺は,
  2^(3(a-1)) * 3^(2(b-1)) * 5^(c-1) * 2^3 * 3^2 * 5
a ≧ 1 , b ≧ 1 , c ≧ 1 より,a-1 ≧ 0 , b-1 ≧ 0 , c-1 ≧ 0 より,
  e = 0
∴2^(3(a-1))*3^(2(b-1))*5^(c-1) * 2^3*3^2*5
 = d * 10^5 + 2^6 * 5 * 23
 = 2^6 * 5 * ((625/2)*d + 23)  ← 2^5でくくるべきだが,3a乗よりOK
したがって,d は2の倍数である.d = 2 , 4 , 6 , 8 を代入して,9の倍数になるのは
  d = 2
のときだ...続きを読む

Q再帰処理を非再帰処理に書き換える場合

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Void Release( PTR* pp );
template <class T> static Void Release( T** pp ){ Release( (PTR*)pp ); }

};


んで

using TreeView::Node::Super;

Super::Super() : next(NULL), child(NULL){}
Super::~Super(){}

こんな感じにしといて、任意に追加、挿入しときますと

その後一括解放のためのReleaseの本体は

Void Super::Release( PTR* pp ){

for ( PTR p; p = *pp; ){
if ( p->child ) Release( &p->child );
*pp = p->next;
delete p;
}

}

こんな感じで、再帰を使えば結構簡単に書けると思うのですが


・・・利用法から考えてよっぽどないとは思うのですが
やはりそこは一応
スタックオーバーフローの危険性をコードサイドから積極的に
ほぼ回避しておくべきと考えると

階層数の上限を設けておいて
最低、追加・挿入時には、それをチェックする

というのが良いかと思うのですが

仮に別のアプローチで
こういった類の再帰(もっと複雑な場合のが多いかも)を非再帰関数に直すには
やっぱり


・goto文
・自分でヒープ上などに作る疑似スタック
・そのスタックに、gotoのジャンプ位置を保存できるenumとかの定数フラグ


などを使用せざるを得ない
って感じになってくるんでしょうかね?

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Voi...続きを読む

Aベストアンサー

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
continue ; // 次へ
}

if ( p->child ) { // 子があったら、
sp.push(p->child) ;// 子をスタックへ積んで
continue ; // 次へ:再帰呼び出しに相当
}

sp.push(p->next); // 次の候補であるp->nextをスタックに積む

*pp = p->next;
delete p;

sp.pop() ; // topは処理済みになるのでスタックから削除

}
}

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
co...続きを読む

Q素因数分解する問題?

√1980B の根号がとれる最も小さい自然数Bを求めよ。

上の問題で
たぶん素因数分解をすると思うのですが、
素因数分解してそのあとがよくわかりません
こんな私にもわかるように説明してほしいです;
よろしくお願いします。

Aベストアンサー

 根号をとれるためには、素因数分解したときの素数の肩にある数(べき乗)が偶数でなければなりません。
 その最も小さい自然数を求める場合は、素数の肩にある数が奇数の素数だけを抜き出して、それらの素数をすべて掛け合わせれば求められます。

 例)√12Cの根号をとる場合:
   12=2^2×3  ← 素数2のべき乗は偶数。素数3のべき乗は奇数。
  ∴C=3

Q再帰関数を用いて配列の合計を求める

かなり(約三時間)悩んでまだ分からないので質問します。
再帰関数を用いて配列の中の数字(floatで定義されている)の合計を求めるプログラムを作っています。階乗を求めるプログラムの例を見ながらやっているのですがもう降参です。簡単だと思ったんですけど配列と組み合わせでもう頭がパニックです。どなたか答え(またはヒント)を教えてください。

よろしくお願いします。
なお、下のプログラムは私が1から作りましたので完全に間違っている可能性大です。参考にしないでください。(^^ゞ

#include <iostream>
using namespace std;

float recur(int numF);

int main()
{
int num;
float sum;

cout << "Enter an integer number: ";
cin >> num;

//再帰関数なんてこうやれば使わなくても出来るのに~!
//for(i=0; i<num; i++)
//sum += array[i];

sum = recur(num);

cout << "The sum of all the numbers: " << sum << endl;

return 0;
}

float recur(int numF)
{
int i;
float array[numF]; //定数式が必要です、と怒られる

for(i=0; i<numF; i++)
return array[i] += array[i-1]; //ここに再帰の式が必要
}

かなり(約三時間)悩んでまだ分からないので質問します。
再帰関数を用いて配列の中の数字(floatで定義されている)の合計を求めるプログラムを作っています。階乗を求めるプログラムの例を見ながらやっているのですがもう降参です。簡単だと思ったんですけど配列と組み合わせでもう頭がパニックです。どなたか答え(またはヒント)を教えてください。

よろしくお願いします。
なお、下のプログラムは私が1から作りましたので完全に間違っている可能性大です。参考にしないでください。(^^ゞ

#include <iostre...続きを読む

Aベストアンサー

#2 です。二つ目、間違えた。

>   return sum(array, num - 1) + array[0];

  return sum(array, num - 1) + array[num - 1];

# 確認してません。って、この間違いを見ても分かるか (^^;

Q正規数と素因数分解に関する証明問題

正規数と素因数分解に関する証明問題です。

xが正規数(1/xが60進有限小数)
⇔x=2^a3^b5^cと素因数分解できる

xが正規数(1/xが12進有限小数)
⇔x=2^a3^bと素因数分解できる

以上2題の証明がどうしてもわかりません。
わかる方、教えてください。

Aベストアンサー

正則数 (reguler number) ですね。
http://mailsrv.nara-edu.ac.jp/~asait/pythagorean/pytha.htm#section211
因みに、正規数 (normal number) は、
http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E6%95%B0 。

証明は、概略 No.1 のような流れだと思いますが。

Q再帰関数とユークリッドの互除法を用いて最大公約数を求める

学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。

#include <stdio.h>

/* 正整数 n, m の最大公約数を計算する */
int gcd(int n, int m) {
int res;

res = n % m;

if (res == 0)
return m;/* 最大公約数が求まった */

return gcd(m, res);/* 再帰呼び出し */
}

int main(void) {
int i,j;

for(i=10000;i>=10;i--){
for(j=10;j=10000;j++){
printf("%d to %d no saidaikouyakusuu ha %d \n", i, j, gcd(i, j));
}
}

return (0);
}

です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。

学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。

#include <stdio.h>

/* 正整数 n, m の最大公約数を計算する */
int gcd(int n, int m) {
int res;

res = n % m;

if (res == 0)
return m;/* 最大公約数が求まった */

return gcd(m, res);/* ...続きを読む

Aベストアンサー

未検証
>for(j=10;j=10000;j++){
少なくとも真ん中の条件の=は誤り。それ以外に思いつくミスは特にない

Q素因数分解 問題

教科書に書いてあった問題です。

1、素因数分解せよ

(1)98   (2)228   (3)720

です。
解き方がよくわかりません。教えてください

Aベストアンサー

素因数分解というのは、素数で表せっていう意味なので
(1) 2×7^2
98を素数(1と自分自身でしか割り切れない数)で割っていって、割り切れないところまで計算するので
   98÷2=49 49は7×7なので、これで終わり。
(2) 2^2×3×19
   228÷2=114 114÷2=57 57÷3=19
(3) 2^4×3^2×5
   720÷2=360 360÷2=180 180÷2=90 90÷2=45 45÷3=15 15÷3=5
となると思います。

Q再帰プログラム

strに格納されている文字数を数えるプログラムです。

#include<stdio.h>

int rstrlen(char *);

int main(void)
{
char str[] = {"abcdefghijk"};
printf("文字数:%d\n",rstrlen(str));
return 0;
}
int rstrlen(char *p)
{
if(*p) {
p++;
printf(p);
return 1 + rstrlen (p);
}
elsereturn 0;
}

return 1 + rstrlen (p);の部分で再帰をし1をプラスすることにより文字数をカウントしmainのprintfで文字数を表示しているのですがカウントしている値はどこに格納していてどのようにmainに返しているのかが分かりませんでした。教えてください。

Aベストアンサー

rstrlen("abc")
→ (1 + rstrlen("bc"))
→ (1 + (1 + rstrlen("c")))
→ (1 + (1 + (1 + rstrlen("")))
→ (1 + (1 + (1 + (0))))
→ (1 + (1 + (1 + 0)))
→ (1 + (1 + (1)))
→ (1 + (1 + 1))
→ (1 + (2))
→ (1 + 2)
→ (3)
→ 3

()が付くのがコール,外れるのがリターンです。
カウントしている値は関数の中に格納されていると言えなくもない。

Qいきなりすみません数学の問題なのですが、√2.01を素因数分解か平方根かは分かりませんが解いたら

いきなりすみません
数学の問題なのですが、
√2.01を素因数分解か平方根かは分かりませんが解いたら1.42という答えになると教材に書いてあり、
どうしてもそれまでの過程の計算が
私には分かりません。
どうか教えてください!お願いします!

Aベストアンサー

√2.01を素因数分解か平方根かは分かりませんが・・・
 素因数分解とか平方数の問題ではないです。
 単純に紙と鉛筆で計算すればよい。一目見て1と2の間ということはわかるでしょうから・・
    _1 4  1  4
1  √ 2.01 00 
1   _1___
24      1 00
 4   ____96__
281       4 00
  1       2 81
2824       1 19 00
  4       1 12 96

 1.41・・・あたりだと計算できる。筆算は習っているとして・・
検算
 1.41
×1.41
1.9881

>解いたら
 ではなく計算したらですよ。
 ^^^^^^^^^^^^^^^^^この用語の違いは数学では最も重要

>どうしてもそれまでの過程の計算が私には分かりません。
 電卓で2.01 → √
 電卓なければ筆算で・・・まあ3桁くらいなら適当な数字を割り当てても出せるでしょう。

Q再帰プログラム

#include<stdio.h>

int rstrlen(char*);

int main(void)
{
char str[100];

printf("文字列を入力してください\n");
gets(str);

printf("文字数は %d です\n",rstrlen(str));

return 0;
}
int rstrlen(char *p)
{
if(*p){
p++;
return 1+rstrlen(p);
}

else
return 0;
}
文字数を計算するプログラムです。
if(*p)の*pとはNULLを表しているのですか?

Aベストアンサー

 「rstrlen」を見てみます。ここには,char へのポインタ p が入って呼び出されます。

 ここでの,if (*p) は,if (*p != '\0') と同じです。ですから,「p の指す先の文字がヌル文字(=終端)でなかったら」です。このとき,p の指す先を 1 だけ増やして,再帰し,その戻り値に 1 を加えます。一方,ヌル文字だったらそこで再帰は停止し,0 を返します。


人気Q&Aランキング

おすすめ情報