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は整数で、しかもaは0でないものとして、
このとき2次式
   ax^2 + bx + c
を、整数係数の範囲で因数分解するプログラムを作る

ことになったのですが、

1.任意のa,b,cの値を入れてもらう。

2.二次方程式の解で
  整数係数の範囲で因数分解できるか判別する。

3.なにかを用いて分解する。

4.結果を表示する。
  (dX + e)(fX + g)のような形で。

とまでは考えられるのですが、
3.の所が難しくて、考えてからかなり時間がたってしまい
らちがあかない感じです。
たすきがけを使うにしても、いまいち、よくわかりません。

どなたか、教えてください。お願いします。

Aベストアンサー

No.3 ですが、計算部分を省略せずに書きます。

x = (-b ± √(b^2 - 4ac)) / 2a
この式をこれ変形させる必要はありません。

実際に、3x^2 + 14x + 8 を順に計算してみます。
a = 3
b = 14
c = 8
このa, b, cの値を代入するわけだから、

x = (-14 ± √(14^2 - 4×3×8)) / 2×3
x = (-14 ± √100) / 6
ここで、±を2つに分けて、
x = (-14 + 10) / 6, x = (-14 - 10) / 6
x = -4 / 6, x = -24 / 6
x = -2/3, x = -4

プログラムとして考えていくと、√(b^2 - 4ac) から考えて、
int q = (b * b - 4 * a * c); // q = 100
int r = sqrt(q); // r = 10
if (r * r != q) { // sqrt の結果が整数でなければ解なし
return 解なし;
}

この後、割り算を計算せずに、分数として別の変数に持ちます。
int n1 = -b + r; // +の分子 (n1 = -4)
int m1 = 2 * a; // 分母 (m1 = 6)

この時点で、(6x + 4) と表示させる事もできますが、なんらかの方法で n1/m1 を約分することで、(3x + 2) と表示させる事は難しくないと思います。

同様に、
int n2 = -b - r; // -の分子 (n2 = -24)
int m2 = 2 * a; // 分母 (m2 = 6)
これも、-24/6 を -4/1 に約分することで (x + 4) と表示できるでしょう。

ここで符号について考えてみると、(3x + 2)(x + 4) の符号を全て反転させて、(-3x - 2)(-x - 4) としたとしても全く同じですが、あえて2つ表示する必要はないのではないかと思います。

No.3 ですが、計算部分を省略せずに書きます。

x = (-b ± √(b^2 - 4ac)) / 2a
この式をこれ変形させる必要はありません。

実際に、3x^2 + 14x + 8 を順に計算してみます。
a = 3
b = 14
c = 8
このa, b, cの値を代入するわけだから、

x = (-14 ± √(14^2 - 4×3×8)) / 2×3
x = (-14 ± √100) / 6
ここで、±を2つに分けて、
x = (-14 + 10) / 6, x = (-14 - 10) / 6
x = -4 / 6, x = -24 / 6
x = -2/3, x = -4

プログラムとして考えていくと、√(b^2 - 4ac) から考えて、
int q = (b * b - 4 *...続きを読む

Q16進数から2進数へ

16進数の文字列を2進数に変換して、int型の配列に1or0で書き込んでいきたいんですが、どうすればいいのかわかりません。よろしくお願いします。

Aベストアンサー

即席ですが。ctype.hとかstdlib.hとか要ると思います。
戻り値>=0で正常終了。その場合は書き込まれた長さ(使った配列の要素数)が返ります。

int hexToBinary(char* src, int* dest) {
char c;
int x, i;
char* p = src;
while(*p != NULL) {
c = tolower(*p);
if (isdigit(c)) {
x = c - '0';
} else if (c >= 'a' && c <= 'f') {
x = c - 'a' + 10;
} else {
return -1;
}
for (i=0; i<4; i++,x>>=1) {
dest[3-i] = x & 1;
}
p++;
dest+=4;
}
return (p-src)*4;
}

Q因数分解プログラム(C言語)について(3)

つづきです
/*求めた最大公約数で約分*/
if(*flag == 1){
*d = *m1 / *i;
*e = *n1 / *i;
}
else{
printf("約分できません。\n");
*d = *m1;
*e = *n1;
}
return 0;
}
int yakubun2(int *m2,int *n2,int *min2,int *flag,int *i,int *f,int *g)
{
/*最大公約数を見つける*/
if(*m2 < *n2){
*min2 = *m2;
}
else{
*min2 = *n2;
}
*flag = 0;
for(*i = min2; *i > 0; *i--){
if(*m2 % *i == 0){
if(*n2 % *i == 0){
*flag = 1;
break;
}
}
}
/*求めた最大公約数で約分*/
if(*flag == 1){
*f = *m2 / *i;
*g = *n2 / *i;
}
else{
printf("約分できません。\n");
*f = *m2;
*g = *n2;
}
return 0;
}
/*因数分解の結果を表示*/
int output(int *d,int *e,int *f,int *g)
{
printf("(%dχ-%d)(%dχ-%d)",*d,*e,*f,*g);
return 0;
}

関連URL:http://www.okweb.ne.jp/kotaeru.php3?q=474597

つづきです
/*求めた最大公約数で約分*/
if(*flag == 1){
*d = *m1 / *i;
*e = *n1 / *i;
}
else{
printf("約分できません。\n");
*d = *m1;
*e = *n1;
}
return 0;
}
int yakubun2(int *m2,int *n2,int *min2,int *flag,int *i,int *f,int *g)
{
/*最大公約数を見つける*/
if(*m2 < *n2){
*min2 = *m2;
}
else{
*min2 = *n2;
}
*flag = 0;
for(*i = min2; *i > 0; *i--){
if(*m2 % *i == 0){
if(*n2 % *i == 0){
*flag = 1;
break;
}
}
}
/*求めた最大公約数で約分*/
if(*flag =...続きを読む

Aベストアンサー

>それから、変数iとflag以外にも

あとは、min1 と min2 だけでしょうか。

課題という事なので、プログラムが正しく動いているかどうかは試していませんが、全体を見て気になった事を・・・

yakubun1 と yakubun2 は同じ内容なので1つにまとめた方がいいです。これについては、bunkai1 と bunkai2 にも同じことが言えます。
1つにまとめると、試行錯誤している段階での修正量が減り、修正ミスも減ります。そして、C 言語の関数への理解度が高い事をアピールできます。
私の場合、ポインタを使って値を返す時、その変数を前に持ってくる事が多いですが、決まりというわけではないです。

yakubun(&d, &e, m1, n1);
yakubun(&f, &g, m2, n2);

void yakubun(int *rm, int *rn, int m, int n)
{
int i;
int flag;
int min;
/* 以下省略 */
}

Q素数判定を再帰処理で

お世話になります。
与えられた数が素数、あるいは素数同士の積かどうかを判定するプログラムを再帰処理で書きたいのですが、どのように書いたらいいのかがわかりません。
素数判定は単に数を2から繰り返し割って、割り切れなければ次は3で繰り返し割って・・・とやればよいと思うのですが、再帰ではどのように書いたらよいのでしょうか。
出力結果は以下のようにしなければなりません。例として1173は素数同士の積かを判定します。

1173 = 391 × 3:これらの数は素数か、あるいは素数同士の積か?
391 = 23 × 17:これらの数は素数か、あるいは素数同士の積か?
23は素数。
17は素数。
よって391は素数同士の積である。(23と17は素数あるいは素数同士の積)
3は素数。
よって1173は素数同士の積である。(391と3は素数あるいは素数同士の積)

次に36でやると、
36 = 18 × 2:これらの数は素数か、あるいは素数同士の積か?
18 = 9 × 2:これらの数は素数か、あるいは素数同士の積か?
9 = 3 × 3:この数は素数か、あるいは素数同士の積か?
3は素数。
9は3の2乗、すなわち素数あるいは素数同士の積である。
2は素数。
よって18は素数同士の積である。(9と2は素数あるいは素数同士の積)
2は素数。
よって36は素数同士の積である。(18と2は素数あるいは素数同士の積)

どなたかわかる方、宜しくお願いします。

お世話になります。
与えられた数が素数、あるいは素数同士の積かどうかを判定するプログラムを再帰処理で書きたいのですが、どのように書いたらいいのかがわかりません。
素数判定は単に数を2から繰り返し割って、割り切れなければ次は3で繰り返し割って・・・とやればよいと思うのですが、再帰ではどのように書いたらよいのでしょうか。
出力結果は以下のようにしなければなりません。例として1173は素数同士の積かを判定します。

1173 = 391 × 3:これらの数は素数か、あるいは素数同士の積か?
391...続きを読む

Aベストアンサー

#5です。
戻り値が int ではなく int[] であることにお気づきですか?
素因数分解する関数とは別に、与えられた数はいくつで割れるのかを計算する関数を示したつもりなのですが。
1173を与えられると、(391と3)を返すのです。

課題でしたか。ではまあ勉強のために、ご自身で書いてみるほうがよいのかな。
こちらでは道筋だけ。なお、素数チェックの関数は#5に上げてあります。
メイン(){
 素因数分解(1173)

void 素因数分解(int prime){
 int[]ret= 素数チェック(prime,2);
 素数なら{
  素数と表示
  return;
 }
 何かの二乗なら{
  素因数分解(ret[0]);
 }
 素因数分解(ret[0]);
 素因数分解(ret[1]);
}

Q16進数を10進数に簡単に変換する関数は?

16進数を10進数に簡単に変換する関数は何かありますか?
もしご存知でしたら教えていただけないでしょうか?

例えば、3BDF8という16進数を10進数に変換したいと思っています。

Aベストアンサー

C言語のプログラム内では、保持している数値にn進数という概念はなく
文字列化するときに初めて考えるものです。

int n; // <- このnは何進数でもない

ご質問を以下のように解釈してサンプルを書いてみました。

例えば、3BDF8という16進数(の文字列)を10進数(の文字列)に変換したいと思っています。


$ cat test.c
#include <stdio.h>

int main(int argc, char *argv[])
{
int num;
sscanf(argv[1], "%x", &num);
printf("%d\n", num);
}

$ ./a.out 3BDF8
245240

いかがでしょうか。

Qセグメンテーション違反

C言語を使用しています。

構造体に値をいれようとしたら、コンパイルは出来るのですが、実行時に
「セグメンテーション違反です (core dumped)」
となってしまい、それ以上行えません。

構造体と代入したい変数との型は、合っています。

いろいろ本などで見ましたが、何が原因かわからず困っています。
教えてください。
宜しくお願いします。

Aベストアンサー

OSは何でしょうか。コンパイラは何を使用していますか?
通常、デバッグオプションをつけて実行すると、異常の発生したソースの箇所で止まりますので、それが手がかりになります。またNo1の方が言われてますように、ソースが公開できるのであれば、ソースを提示するのが良いかと思います。

QC言語 再帰処理のメリットとデメリット

最近、C言語の関数にも再帰定義ができるということを初めて知りました。
そこで聞きたいのですが、再帰処理のメリット・デメリットは何でしょうか?
思いついたものとしては

メリット … 簡単に表記できる
デメリット … 無限ループが発生する可能性あり

でしょうか。
また、全計算が終わるまでに、途中の演算結果を保持しなければならないので、
メモリを無駄遣いしそうな気もします。

Aベストアンサー

「メリット … 簡単に表記できる」

これはケースバイケースなのではないでしょうか。例えば配列の要素の和を求めるなんてのは、普通にループで書いた方が簡単です。一方、フィボナッチ数列を求めるなんてのは(教科書的な例で恐縮です。私が書いた中では、ある種の文法解析)再帰で書いた方が簡単でキレイですよね。

「デメリット … 無限ループが発生する可能性」

これは単に、繰り返しの終了条件の書き方の問題ではないでしょうか。普通の for などのループでも終了条件を間違えれば、同じだと思います。ただ再帰処理だと、終了条件が普通の if 文だったりするので、見た目が少し分かり難いという程度でしょう。

一部のプログラミング言語、例えば lisp とか prolog、では再帰処理をコンパイラが普通にループの繰り返しに変換して処理速度を上げています(ただし可能な場合のみ、全ての再帰処理をループに変換できない)。まあ prolog だと for のような繰り返しがなかったりする、という事情もあるのですが。

しかし、C ではそれをやらない約束になっているようです。ということで、再帰処理だとスタックが繰り返しの回数に比例して延びてしまいますので、無限ループは書く事ができませんし、繰り返し回数が多いとスタックが溢れたりします。もちろん、for などの普通の繰り返しの方が、再帰呼び出しよりも速いです(だから一部の言語では再帰をループに変換する)。

ということで、デメリットとしては、「遅い、メモリを喰う」という事になるかと思います。

No.1 さんのご回答にあるように、スレッドを細かい粒度にして並列度を上げるために、ループの繰り返しの単位で並列に処理しようとする、つまり、再帰呼び出しの関数レベルでスレッドにしたくなる気持ちは分かりますし、そういう研究は昔から多くあります。

しかしながら、実際問題、こうして並列度を上げてもなかなか速くならないようです。それよりも大きな配列を分割して並列化する方が、今の段階だと、ずっと簡単に速くなるようです。ただし、近い(?)将来、マルチコアが 100 とかいうレベルになると状況が変わるかもしれません。

「メリット … 簡単に表記できる」

これはケースバイケースなのではないでしょうか。例えば配列の要素の和を求めるなんてのは、普通にループで書いた方が簡単です。一方、フィボナッチ数列を求めるなんてのは(教科書的な例で恐縮です。私が書いた中では、ある種の文法解析)再帰で書いた方が簡単でキレイですよね。

「デメリット … 無限ループが発生する可能性」

これは単に、繰り返しの終了条件の書き方の問題ではないでしょうか。普通の for などのループでも終了条件を間違えれば、同じだと思います。...続きを読む


人気Q&Aランキング