掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.26380

2進数の表記
投稿者---まぁ(2006/03/10 18:16:30)


再帰を使って
00
01
10
11
というように2進数を表記するプログラムを作りたいのですが、自分で考えていてもちっともうまくいきません。
ネットや本などで順列生成などプログラムを参考にしながら自分なりに考えたのですが、最初の00が表示されるだけです。
考え方自体が間違っているのでしょうか?
それとも、まだC言語に不慣れなために初歩的な間違いをくり返してしまっているのか・・・それさえもわからないくらい頭が混乱してしまいました。
どなたか、アドバイスをお願いします。

#include<stdio.h>
#define N 2

int a[N];

void bin(int i)
{
if(a[1]<=1){
for(i=N;i>=0;i--){
if(a[i]==0||a[i]==2){
a[i]=1;
bin(i-1);
}else{
a[i]=0;
a[i-1]++;
a[i]<=1;
}
}
}else{
printf"%d",a[i]);
}
}
main()
{
int i;
printf("2進数の表記\n");
for(i=N;i>=1;i--){
a[i]=0;
printf("%d",a[i]);
}
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:2進数の表記 26381 iijima 2006/03/10 19:21:17
<子記事> Re:2進数の表記 26382 iijima 2006/03/10 20:42:26
<子記事> Re:2進数の表記 26383 iijima 2006/03/10 20:44:51


No.26381

Re:2進数の表記
投稿者---iijima(2006/03/10 19:21:17)


# うーん、どこから手をつけたらよいか...

まず、配列の要素数と要素番号の関係。
Nを2と定義していますから、a[N]配列の要素数は2です。
これで確保された配列の要素番号は0,1です(1,2ではありません)。
a[0]とa[1]のみが正しいアクセスであって、a[2]やa[-1]は不正な場所へのアクセス
となります。
main関数のfor文内のiの値は、2(=N)から1まで変化しますから、i=2のときに不正な
アクセスをしています。
N=2のとき、a[i]のiの値は、01(=N-1)でなくてはなりません。

次に、関数呼び出しについて。
bin関数は何らかの引数を受け取って、再帰によってa[0]とa[1]に2進数表示のための
値(01)を設定することを意図しているのだと思いますが、main関数のどこからも
bin関数を呼び出していません。
関数は、main関数(あるいはmain関数から呼び出された関数)内から呼び出さなけれ
ば実行されません。
今のmain関数内では、a[i]=0としたあと、すぐにa[i]の値を表示させているのですか
ら、繰り返しの間'0'が表示されるのは当然です。
# しかも、前述のようにi=2のときは不正な場所にアクセスしていますから、動い
# ているのはたまたまのことです。

これらを理解したうえで、bin関数は何を引数にし、main関数からどのように呼び出
せば良いか、つまりbin関数の仕様を考えます。
2桁の二進数0011(十進数では03)を表示させたいということですから、引数は
元の値(03)ということではありませんか?

だとすれば、main関数からのbin関数の呼び出し及びaの表示は、次のようにするのが
妥当だと思います。

    for( i = 0; i <= 3; i++){
        bin( i ); // ここでiの値に基づきa[0],a[1]の値を設定する。
        for( j = N - 1; j >= 0; j-- ){
            printf( "%d", a[j] );
        }
        printf( "\n" );
    }
  // jをN-1から降順で繰り返すか、0から昇順で繰り返すかは、bin関数
  // の定義による

bin関数の定義にも問題がありますが、それを考えるのは、ここまでを理解して頭の
整理ができてからですね。

関数呼び出しの要領を体感するには、bin関数の中身を次のようにして、上のfor文
によって呼び出すプログラムを書いて実行して処理の順番をひとつひとつ追いかけ
てみると良いかもしれません。

void bin( int n )
{
    a[0] = n;
    a[1] = n + 1;
}



この投稿にコメントする

削除パスワード

No.26382

Re:2進数の表記
投稿者---iijima(2006/03/10 20:42:26)


追記:
ちょっとbin関数の定義を考えてみたのですが、引数として配列の要素番号を渡す必要が
ありそうです。
プロトタイプは次のとおり。

void bin( int n, int i );
// n:二進数表示にしたい数
// i:配列の要素番号(0〜N-1)

それから、main関数からbin関数を呼び出す直前に、毎回aの全ての要素を0にする処理
も必要ですね。

bin関数定義のヒントとしては、例えば、元の数が3のとき、

1回目の呼び出し n ← 3, i ← 0
a[ i ] ← n % 2 = 1

2回目の呼び出し n ← n / 2 = 1, i ← i + 1 = 1
a[ i ] ← n % 2 = 1

3回目の呼び出し n ← n / 2 = 0, i ← i + 1 = 2
N <= i → 終了

# あくまでも一例です。



この投稿にコメントする

削除パスワード

No.26383

Re:2進数の表記
投稿者---iijima(2006/03/10 20:44:51)


ごめんなさい。この処理↓は要りませんでした。

> それから、main関数からbin関数を呼び出す直前に、毎回aの全ての要素を0にする処理
> も必要ですね。



この投稿にコメントする

削除パスワード

No.26385

Re:2進数の表記
投稿者---まぁ(2006/03/11 02:41:47)


説明を読んで考え直したら、支離滅裂なプログラムで恥ずかしいです。
こんな状態にもかかわらず、丁寧な説明ありがとうございました。

そして、bin関数の定義のところでまたつまづいてしまったのですが・・・
表示したい数を2で割ったあまりをa[i]に入れて。その割ったものをまた2で割ってあまりをa[i-1]に入れて・・・という手順が再帰になるから、それをプログラムで書くということでしょうか?

できればもう少し、アドバイスをくださればと思います。

理解が悪くて・・・丁寧に説明していただいているのにすみません。。。


この投稿にコメントする

削除パスワード

No.26386

Re:2進数の表記
投稿者---かずま(2006/03/11 04:33:53)


単純なサンプルプログラムを見て、理解してみようとするのも一つの手です。
理解しないとダメですよ。
#include <stdio.h>

#define N  4

char a[N];

void bin(int i)
{
    if (--i >= 0) {
        a[i] = '0';  bin(i);
        a[i] = '1';  bin(i);
    } else {
        for (i = N; --i >= 0; ) putchar(a[i]);
        putchar('\n');
    }
}

int main(void)
{
    bin(N);
    return 0;
}



この投稿にコメントする

削除パスワード

No.26387

Re:2進数の表記
投稿者---iijima(2006/03/11 09:15:30)


> 表示したい数を2で割ったあまりをa[i]に入れて。
> その割ったものをまた2で割ってあまりをa[i-1]に入れて・・・
> という手順が再帰になる

まず、紙と鉛筆で十進数を二進数に変換する手続きを考えてください。
# 紙と鉛筆は混乱した頭を整理するための必須アイテムです。>私の場合^^

例:十進数の6の場合
[0]回目:元の数   6÷2=商3余り0 余りを2進数の[0]桁目とする
[1]回目:1回目の商3÷2=商1余り1 余りを2進数の[1]桁目とする
[2]回目:2回目の商1÷2=商0余り1 余りを2進数の[2]桁目とする
[2][1][0]の順番で並べると、6の二進数110が得られる。
※桁に入れる順番を逆にすれば、二進数の表示は[0][1][2]の順となる。

いろいろな数で確かめてください。
この手順をしっかり理解した上で、それをプログラムにしていきます。

# 再帰関数でなくても書けます、といより再帰でない方が分かりやすいと思うのですが、
# 再帰の練習/課題なんですかね。



この投稿にコメントする

削除パスワード

No.26397

Re:2進数の表記
投稿者---まぁ(2006/03/12 02:04:51)


どのように動いていくかを書き出していたら、少しずつイメージつかめてきました。
ありがとうございました。

再帰で考えると余計に頭ごちゃごちゃになってしまうんですけど、再帰の練習課題なのでちゃんと理解してプログラム書けるように頑張ります。


この投稿にコメントする

削除パスワード

No.26398

Re:2進数の表記
投稿者---iijima(2006/03/12 11:56:44)


> 少しずつイメージつかめてきました。

それはなにより^^

> 再帰で考えると余計に頭ごちゃごちゃになってしまう

多くの場合、繰り返しと再帰は相互に置き換えることが可能です。
ですから、再帰でない関数を先に考えてみるのも良いかも知れません。
参考までに非再帰関数の例。

int a[ N ];

void bin( int n )
{
    int i;
    for( i = 0; i < N; i++ ){
        a[ i ] = n % 2;
        n /= 2;
    }
}

それから、かずまさんのサンプルは再帰を理解するための良い訓練になると思います。
そちらもよく研究してください。



この投稿にコメントする

削除パスワード

No.26400

Re:2進数の表記
投稿者---再帰は簡素に(2006/03/12 16:03:44)


再帰の考え方

関数binput(val,n)の仕様
valの値を2進数n桁で表示する

実装
最左端の桁はvalを2^(n-1)で割った値
残りの n-1桁は
valを2^(n-1)で割った剰余を2進数n-1桁であらわしたもの

再帰のコツ
多少リソースや計算コストの増大は気にしない。

/*
    Binput Source
*/

#include <stdio.h>

#define N 2

void binput(int val, int len)
{
    if (len > 1 ){
        printf ("%d",val/(1<<(len-1)));
        binput( val % (1<<(len-1)),len-1);
    }else{
        printf ("%d\n",val);
    }
}

int main( void )
{
    int i,len;
    
    len = N;
    for( i=0;i<(1<<len);i++){
        binput(i,len);
    }
    return 0;
}





この投稿にコメントする

削除パスワード

No.26409

Re:2進数の表記
投稿者---まぁ(2006/03/13 01:55:01)


非再帰のプログラムが書けました!
iijimaさん、ありがとうございました。

また、かずまさんのプログラムは最初見たときはどうして動くのか「?」ばかりでしたが、プログラムがどう動くかを書きだしてみたら納得。
そして、ただただ感心・・・発想の転換というか、ひらめかないと書けないと思いました。
自分の力でこのプログラムが思いつけるようになるにはいつになることやら・・・

再帰は簡素にさんのプログラムは<<が分からないので、また「?」ばかりです。
ただ、再帰と一口に言っても、いろいろな方法で書けるんですね。
HPに戻ってまた勉強します。


この投稿にコメントする

削除パスワード

No.26410

Re:2進数の表記
投稿者---かずま(2006/03/13 02:17:24)


> 再帰は簡素にさんのプログラムは<<が分からないので、また「?」ばかりです。

これなら分かりますか?
#include <stdio.h>

#define N  3

void binput(int val, int len)
{
    if (--len > 0) {
        printf("%d", val >> len & 1);
        binput(val, len);
    } else
        printf("%d\n", val & 1);
}

int main(void)
{
    int i;
    for (i = 0; i < 1<<N; i++)
        binput(i, N);
    return 0;
}



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧