C言語関係掲示板

過去ログ

No.915 再帰を用いず、スタックを用いて解く

[戻る] [ホームページ]
No.11606

スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---ミカ(2004/01/09 21:52:00)


本当に申し訳ないのですが、以下の変更前のプログラムを関数の部分だけをスタックを用いて解くのですが最後に61と表示するはずなのですが上手くできません。

-変更前-

<pre>#include&lt;stdio.h&gt;

int F(int n){
int b,c;

if(n&lt;=1){
b=n;
}
else{
b=2*F(n-1)+3*F(n-2);
}
return b;
}

int main(void){
int x;
x=F(5);
printf(&quot;%d&quot;,x);
return 0;
}



-変更後(スタック利用)-

<pre>#include&lt;stdio.h&gt;
#define MAX 10

int sp=-1;
int P[MAX];

void display(int s){
int i;
for(i=0;i&lt;=s;i++){
printf(&quot;P[%d]=%d &quot;,i,P[i]);
}
printf(&quot;\n&quot;);
}

int push(int k){
sp++;
P[sp]=k;
display(sp);
}

void pop(void){
sp--;
display(sp);
}

int top(void){
return P[sp];
}

int empty(void){
if(sp==-1){
return 1;
}
else{
return 0;
}
}

int F(int n){
int b,c;
int r,q;

FBODY:
if(!empty()){
r=top(); pop();
n=top();
push(r);
}

if(n&lt;=1){
q=n;
}
else{
push(n-1);
push(1);
goto FBODY;
C1:
b=top()*2;
pop();
push(n-2);
push(2);
goto FBODY;
C2:
c=top()*3;
pop();
}

if(empty()){
return b+c;
}
else{
pop(); pop();
push(q);
switch(r){
case 1: goto C1;
case 2: goto C2;
}
}
}

int main(void){
int x;
x=F(5);
printf(&quot;%d&quot;,x);
return 0;
}




No.11607

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---てつや(2004/01/09 22:05:24)


このHPの上の方に【掲示板ご利用上の注意】というのがありますので一読される事をお勧めします。

>ソースを添付する際には.....
↑私が言いたいのはこれ

No.11618

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---ミカ(2004/01/10 14:19:49)


すいませんこちらでございます。よろしくお願いします。


#include<stdio.h>

int F(int n){
int b,c;

if(n<=1){
b=n;
}
else{
b=2*F(n-1)+3*F(n-2);
}
return b;
}

int main(void){
int x;
x=F(5);
printf("%d",x);
return 0;
}



-変更後(スタック利用)-

#include<stdio.h>
#define MAX 10

int sp=-1;
int P[MAX];

void display(int s){
int i;
for(i=0;i<=s;i++){
printf("P[%d]=%d ",i,P[i]);
}
printf("\n");
}

int push(int k){
sp++;
P[sp]=k;
display(sp);
}

void pop(void){
sp--;
display(sp);
}

int top(void){
return P[sp];
}

int empty(void){
if(sp==-1){
return 1;
}
else{
return 0;
}
}

int F(int n){
int b,c;
int r,q;

FBODY:
if(!empty()){
r=top(); pop();
n=top();
push(r);
}

if(n<=1){
q=n;
}
else{
push(n-1);
push(1);
goto FBODY;
C1:
b=top()*2;
pop();
push(n-2);
push(2);
goto FBODY;
C2:
c=top()*3;
pop();
}

if(empty()){
return b+c;
}
else{
pop(); pop();
push(q);
switch(r){
case 1: goto C1;
case 2: goto C2;
}
}
}

int main(void){
int x;
x=F(5);
printf("%d",x);
return 0;
}



No.11628

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---ミカ(2004/01/10 20:27:02)


いちおうこういう風になりましたが、もう少しなのですが上手くいきません。お願いします、教えていただけないでしょうか。
#include<stdio.h>
#define MAX 10

int sp=-1;
int P[MAX];

void display(int s){
int i;
for(i=0;i<=s;i++){
printf("P[%d]=%d ",i,P[i]);
}
printf("\n");
}

int push(int k){
sp++;
P[sp]=k;
display(sp);
}

void pop(void){
sp--;
display(sp);
}

int top(void){
return P[sp];
}

int empty(void){
if(sp==-1){
return 1;
}
else{
return 0;
}
}

int F(int n){
int b,c=0;
int r;

FBODY:
if(!empty()){
r=top(); pop();
n=top();
push(r);
}

if(n<=1){
b=n;
}
else{
push(n-1);
push(1);
goto FBODY;
C1:
c=top()*2;
pop();
push(n-2);
push(2);
goto FBODY;
C2:
c=top()*3;
pop();
}

if(empty()){
return b+c;
}
else{
pop(); pop();
push(b+c);
switch(r){
case 1: goto C1;
case 2: goto C2;
}
}
}

int main(void){
int x;
x=F(5);
printf("%d",x);
return 0;
}


No.11631

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---あかま(2004/01/10 21:35:06)


てつやさんが言っているのはHTML変換ツールを使って投稿してね。
ということですよ。

で、あと問題自体が不明確なのですがスタックを使って解くというのは再帰を使わないということですか?


とりあえず字下げしてみましたがgotoが多くて読めず。
forかwhileに書き直すことをおすすめします。
#include<stdio.h>
#define MAX 10

int sp=-1;
int P[MAX];

void display(int s){
    int i;
    for(i=0;i<=s;i++){
        printf("P[%d]=%d ",i,P[i]);
    }
    printf("\n");
}

int push(int k){
    sp++;
    P[sp]=k;
    display(sp);
}

void pop(void){
    sp--;
    display(sp);
}

int top(void){
    return P[sp];
}

int empty(void){
    if(sp==-1){
        return 1;
    }
    else{
        return 0;
    }
}

int F(int n){
    int b,c=0;
    int r;
    
FBODY:
    if(!empty()){
        r=top(); pop();
        n=top();
        push(r);
    }
    
    if(n<=1){
        b=n;
    }
    else{
        push(n-1);
        push(1);
        goto FBODY;
C1:
        c=top()*2;
        pop();
        push(n-2);
        push(2);
    goto FBODY;
C2:
        c=top()*3;
        pop();
    }
    
    if(empty()){
        return b+c;
    }
    else{
        pop(); pop();
        push(b+c);
        switch(r){
            case 1: goto C1;
            case 2: goto C2;
        }
    }
}
    
int main(void){
    int x;
    x=F(5);
    printf("%d",x);
    return 0;
}




この投稿にコメントする

削除パスワード

No.11632

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---ミカ(2004/01/10 21:50:21)


そうです。再帰を使わないで goto などを用いて解くのです。意味がわからないプログラムですが、学校の課題なので文句が言えないのです。お願いします力を貸してください。

No.11641

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---たか(2004/01/10 23:57:00)


>そうです。再帰を使わないで goto などを用いて解くのです。意味がわからないプログラムですが、学校の課題なので文句が言えないのです。お願いします力を貸してください。

ここにすごくよく似た内容の
講義例が載っていますが、これ見て解けませんか。


No.11642

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---たか(2004/01/10 23:59:42)


基本的に自分自身を2回以上呼び出している再帰関数を非再帰版に
直すのは難しいですねえ。私自身もやった事がありません。
ものの本によれば可能であると書いてありますが具体例がなかなか見つ
からなくて。

No.11644

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---たか(2004/01/11 00:27:45)


寝る前にもう一つ。ここ

No.11645

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---RAPT(2004/01/11 00:39:17)


やってみました。一応、スタック使っています(笑)。
しかし、先生に見せたら怒られるでしょう、きっと。

#include <stdio.h>
#include <stdlib.h>

#define MAX 10
int stack[1+MAX];
int count = 0;

void push(int value){
  if (count >= MAX){
    fprintf(stderr, "[error] stack overflow.\n");
    exit(1);
  }
  stack[count++] = value;
}
int pop(){
  if (count < 1){
    fprintf(stderr, "[error] stack no more values.\n");
    exit(1);
  }
  return stack[--count];
}

int F(int max){ // 0 1 2 7 20 61;

  int a = 0, b = 1, i;
  for(i = 0; i < max; i++){
    push(a * 3 + b * 2);
    a = b;
    b = pop();
  }
  return a;
}

int main(void){
  int i;
  for (i = 0; i < 10; ++i){
    printf("F(%d)=%d\n", i, F(i));
  }
  return 0;
}


No.11662

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---ミカ(2004/01/11 16:57:19)


すいません。問題を間違えてました。 再帰関数が二つあるときの処理の仕方がわからないのです。

-変更前-

#include<stdio.h>
#define MAX  10

int sp=-1;
int P[MAX];

void display(int s){
  int i;
  for(i=0;i<=s;i++){
    printf("P[%d]=%d  ",i,P[i]);
  }
  printf("\n");
}

int push(int k){
  sp++;
  P[sp]=k;
  display(sp);
}

void pop(void){
  sp--;
  display(sp);
}

int top(void){
  return P[sp];
}

int empty(void){
   if(sp==-1){
    return 1;
 }
   else{
    return 0;
 }
}

int F(int n){
  int b=0,c=0;

  if(n<=1){
    b=1;
  }
  else{
    b=2*F(n-1)+3*F(n-2);
  }
  return b;
}

int main(void){
  int x;
  x=F(5);
  printf("%d",x);
  return 0;
}


-変更後-

#include<stdio.h>
#define MAX  100

int sp=-1;
int P[MAX];

void display(int s){
  int i;
  for(i=0;i<=s;i++){
    printf("P[%d]=%d  ",i,P[i]);
  }
  printf("\n");
}

int push(int k){
  sp++;
  P[sp]=k;
  display(sp);
}

void pop(void){
  sp--;
  display(sp);
}

int top(void){
  return P[sp];
}

int empty(void){
   if(sp==-1){
    return 1;
 }
   else{
    return 0;
 }
}

int F(int n){
  int b,c,d=1;
  int r,z=0;

 FBODY:
  if(!empty()){
    r=top(); pop();
    n=top();
    push(r);
  }

  if(n<=1){
    b=1;
  }
  else if(k==0){
    push(n-1);
    push(1);
    goto FBODY;
  C1:
    b=top()*2;
    pop();
    push(n-2);
    push(2);
    goto FBODY;
  C2:
    push(b);
    c=top()*3;
    pop();
    z=z+c;
    r=1;
  }

  if(empty()){
    return b;
  }
  else{
    pop(); pop();
    push(b);
    switch(r){
    case 1: goto C1;
    case 2: goto C2;
    }
   }
}

int main(void){
  int x;
  x=F(5);
  printf("%d",x);
  return 0;
}


No.11674

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---39(2004/01/11 23:58:59)


たしかにこれは難しいね。タカさんの資料見てもなんかぜんぜんわからないよ。  意味ないカキコで申し訳ないです。

No.11691

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---かずま(2004/01/12 14:47:21)


int F(int n)
{
    int i, s = 1;
    for (i = 0; i < n; i++) s *= 3;
    return (n & 1) ? (s - 1) / 2 : (s + 1) / 2;
}
再帰は使っていませんが、スタックを使っていないので、課題の解答とはなりません。

No.11711

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---てつや(2004/01/13 12:49:22)


休みの間にスレがすごく伸びてますね。
説明は難しいので、作ってみました。
参考にどうぞ。

#include <stdio.h>

static int nStack[1000];
static int nIndex = -1;

static void push(int nValue){ nStack[++nIndex] = nValue; }
static int  pop (          ){ return nStack[nIndex--];   }

int tetuya( int n)
{
    int nValue;
    int nFlag;
    int nTotal;

    /* 開始ポイント*/
    push(n);
    push(99);

MAIN:
    nFlag  = pop();
    nValue = pop();
    push(nValue);
    push(nFlag );

    if(nValue>1){
        push(nValue-1);
        push(1       );
        goto MAIN;
    }

    nFlag  = pop();
    nValue = pop();

    switch(nFlag){
    case 99:
        /* 開始ポイントのみ */
        return nValue;
    case 1:
        /* 左がわの計算終了 */
        nTotal = nValue*2;
        nFlag  = pop();
        nValue = pop();
        break;
    case 2:
        /* 右がわの計算 */
        nTotal = nValue*3;

        /* 回答が出た部分まで計算 */
        while(1){
            nFlag  = pop();
            nValue = pop();

            if(nFlag>=0) break;

            nTotal += nValue;
            if(nFlag==-1 ) nTotal *=2;
            if(nFlag==-2 ) nTotal *=3;
            if(nFlag==-99) return nTotal;
        }
        break;
    default:
        return -1; /* エラー */
    }

    /* 現在求まった答えをpush */
    push(nTotal  );
    push(-nFlag  );
    /* 右の計算開始 */
    push(nValue-2);
    push(2       );

    goto MAIN;
}

int F(int n){
    int b;
    
    if(n<=1){
        b=n;
    }
    else{
        b=2*F(n-1)+3*F(n-2);
    }
    return b;
}


void main(){
    int i;

    for(i=-5; i<25; i++){
        printf( "[%2d] %12d : %12d \n",i, F(i), tetuya(i));
    }
}


No.11712

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---てつや(2004/01/13 13:33:06)


少し修正、こっちの方が利にかなってますね。

int tetuya( int n)
{
    int nValue;
    int nFlag;
    int nTotal;

    /* 開始ポイント*/
    push(n);
    push(99);

MAIN:
    nFlag  = pop();
    nValue = pop();
    push(nValue);
    push(nFlag );

    if(nValue>1){
        push(nValue-1);
        push(1       );
        goto MAIN;
    }

    /* 回答が出た部分まで計算 */
    nTotal = 0;
    nFlag  = -1*pop();
    nValue =    pop();

    do{
        nTotal += nValue;
        if(nFlag==-1 ) nTotal *=2;
        if(nFlag==-2 ) nTotal *=3;
        if(nFlag==-99) return nTotal;

        nFlag  = pop();
        nValue = pop();
    }while(nFlag<0);

    /* 現在求まった答えをpush */
    push(nTotal  );
    push(-nFlag  );
    /* 右の計算開始 */
    push(nValue-2);
    push(2       );

    goto MAIN;
}




No.11723

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---NykR(2004/01/13 17:32:51)


機械的に置き換えただけですが。

#include <assert.h>

#define MAX_DEPTH 30

#define NUM_OF_INT_EXPR 2

typedef enum {
    ROOT,
    RETURNING1,
    RETURNING2
} ReturnAddress;

typedef struct {
    ReturnAddress       retadrs;   /* 復帰情報 */
    int n;                         /* 引数     */
    int b, c;                      /* ローカル変数 */

#if  NUM_OF_INT_EXPR
    int int_expr[NUM_OF_INT_EXPR]; /*  int型の式   */
#endif

} StackItem;

StackItem stack[MAX_DEPTH];
StackItem *ptr = stack;

void push(StackItem item)
{
    *ptr++ = item;
}

int has_item()
{
    return ptr > stack;
}

StackItem pop()
{
    if (!has_item())
        return *stack;

    return *--ptr;
}

int F(int n)
{
    StackItem   item_self;
    StackItem   item_child;

    item_self.retadrs = ROOT;
    item_self.n = n;
    push(item_self);
    goto CALL;

  CALL:
    item_self = pop();
    if (item_self.n <= 1) {
        item_self.b = item_self.n;
        push(item_self);
        goto RETURNING;
    } else {
        push(item_self);

        item_child.retadrs = RETURNING1;
        item_child.n = item_self.n - 1;
        push(item_child);
        goto CALL;
    }

  RETURNING:
    switch (item_self.retadrs) {
    case ROOT:
        return item_self.b;

    case RETURNING1:
        item_child = pop();
        item_self = pop();
        item_self.int_expr[0] = item_child.b;
        push(item_self);

        item_child.n = item_self.n - 2;
        item_child.retadrs = RETURNING2;
        push(item_child);
        goto CALL;

    case RETURNING2:
        item_child = pop();
        item_self = pop();
        item_self.int_expr[1] = item_child.b;
        item_self.b = item_self.int_expr[0] * 2 + item_self.int_expr[1] * 3;
        push(item_self);
        goto RETURNING;

    default:
        assert(0);
    }
}


No.11726

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---ミカ(2004/01/13 18:33:58)


すいません。昼からずっと分析していますが全然わかりません。かれこれ6時間悩んでます。

No.11735

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---NykR(2004/01/13 22:56:46)


関数呼び出しは、通常以下のように行われます。
#規格で決まっているわけではありませんが。

1. 仮引数(実引数ではない)、復帰情報(どこで呼び出されたかという情報)、
   呼び出し先のローカル変数
   がスタックに積まれる。

2. 呼び出す。

3. 関数内の処理、
   呼び出し元がスタックに積んだ情報を
   参照したり、変更可能であれば変更したりできる。
   このとき、計算途中のデータなどもスタックに積まれる。
   etc.

4. 復帰情報に従って呼び出し元に戻る

5. スタックから1.で積んだデータを取り除く


私のプログラムとの関係は、

1. push(item_child);
2. goto CALL;
3. item_self = pop(); ...... push(item_self);
4. goto RETURNING;
5. pop(item_child);

です。
# Fの冒頭の処理は
#  item_child.retadrs = ROOT;
#  item_child.n = n;
#  push(item_child);
# とすべきだったかもしれません。

ただし、3.で計算途中のデータを積むのは面倒なので、
代わりに1.で場所だけ確保しておいて、3.で書き換えるようにしました。
再帰呼び出しを機械的に置き換えただけなので、あとはそれほど難しくないと思います。

#って、6時間ということは私のプログラムがわからないという話ではないですよね。

No.11746

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---かずま(2004/01/14 14:01:15)


単純化してみました。絵を描いて動きを追ってみてください。
int stack[100], sp;
void push(int i) { stack[sp++] = i; }
int pop(void) { return stack[--sp]; }

int F(int n)
{
    int b;
    push(0);
F0: if (n <= 1) b = 1;
    else {
        n--;  push(1);  goto F0;
F1:     n--;  push(b);  push(2);  goto F0;
F2:     n += 2;  b = 2 * pop() + 3 * b;
    }
    switch (pop()) {
    case 1: goto F1;
    case 2: goto F2;
    }
    return b;
}

----------------------------------------------------------------------
最初の問題だと、
F0: if (n <= 1) b = n;


No.11755

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---かずま(2004/01/14 16:34:27)


int F(int n)
{
    int b;
    for (push(0); ; ) {
        while (n > 1) n--, push(1);
        for (b = 1; ; ) {
            switch (pop()) {
            case 1:  n--;  push(b);  push(2);  break;
            case 2:  n += 2; b = 2*pop() + 3*b; continue;
            default: return b;
            }
            break;
        }
    }
}

goto を使わないように書き直してみましたが、これから、

  F(0) = F(1) = 1
  F(n) = 2*F(n-1) + 3*F(n-2)
  
であることを理解するのは難しいでしょう。


No.11757

Re:スタックを用いたもんだいなのですが。。。(学校の課題)
投稿者---かずま(2004/01/14 17:39:00)


スタックを有効利用して、さらに単純化。
int F(int n)
{
    int b;
    for (push(0), push(1); ; )
        switch (pop()) {
        case 1: for (b = 1; n > 1; n--) push(2); break;
        case 2: n--;  push(b); push(3); push(1); break;
        case 3: n += 2;  b = 2 * pop() + 3 * b;  break;
        default: return b;
        }
}