回 帖 发 新 帖 刷新版面

主题:递归和非递归算法

编写将十进制正整数n转换为k(2=<k=<9)进制数的递归和非递归算法!(C++语言描述)
小弟想请教各位老师这个问题。请给出算法,谢谢各位了![em2]

回复列表 (共14个回复)

沙发

递归:

void print(int n,int k)//将十进制n,以k进制打印出来
{
  if(n<k)
    printf("%d",n);
  else
  {
    print(n/k,k);
    printf("%d",n%k);
  }
}

非递归就用栈,其实语言对递归的支持就是这么做的,实质是一样的

栈的定义我不写了

void print(int n,int k)
{
  Stack *s=new Stack;
  int t;
  while(n)
  {
    s->push(n%k);
    n/=k;
  }
  while(!s->empty())
  {
    s->pop(t);
    printf("%d",t);
  }
}

板凳

递归:

void print(int n,int k)//将十进制n,以k进制打印出来
{
  if(n<k)
    cout<<n;
  else
  {
    print(n/k,k);
    cout<<(n%k);
  }
}

非递归就用栈,其实语言对递归的支持就是这么做的,实质是一样的

栈的定义我不写了

void print(int n,int k)
{
  Stack *s=new Stack;
  int t;
  while(n)
  {
    s->push(n%k);
    n/=k;
  }
  while(!s->empty())
  {
    s->pop(t);
    cout<<t;
  }
}
 
将1楼的改成这样,行吗?

3 楼

谢谢大家的帮忙!我想问一下(非递归就用栈,其实语言对递归的支持就是这么做的,实质是一样的

栈的定义我不写了)
如果要把非递归的算法写全了!要怎么写呢?
呵呵!
递归:
void print(int n,int k)//将十进制n,以k进制打印出来
{
  if(n<k)
    printf("%d",n);
  else
  {
    print(n/k,k);
    printf("%d",n%k);
  }
}
 这是递归的算法,那非递归呢?谢谢了!我今天刚预习完这部分!请教!

4 楼

我已经写很清楚了,你不会想把代码一拷贝就完事吧,栈如何实现的看书,栈不知如何写怎么做栈应用的题呢?

5 楼


[em8][em21][em54]谢谢了,我是自学的这内容。我们现在大一还不开这课程,不过谢谢老师的提醒。呵呵。

6 楼

我没有其它意思,栈这个东西确实是基本的东西,你说你是自学,而且是大一,不错啊,我也是大一自学的,可以拿本好书来看,置顶有几个自学网站,可以参考一下。可以看清华大学出版的《数据结构C语言版》

7 楼

#include <stdio.h>
#define N 8
void tran(int num,int k)
{
    int arr[N],i;
    for (i=0;i<N;i++)
    {
        arr[i]=num%k;
        num=num/k;
        if (num==0)
            break;
    }
    printf("转换为%d进制数为: ",k);
    for (;i>=0;i--)
        switch (arr[i])
        {
        case 10: printf("A");break;
        case 11: printf("B");break;
        case 12: printf("C");break;
        case 13: printf("D");break;
        case 14: printf("E");break;
        case 15: printf("F");break;
        default: printf("%d",arr[i]);
        }
    printf("\n\n\n");
}
void main()
{
    int num,choo;
loop:    printf("请选择功能:0.退出  1.十进制转二进制   2.十进制转八进制  3.十进制转十六进制\n");
        scanf("%d",&choo);
        switch (choo)
        {
        case 1:
            printf("请输入要转换的十进制数:");
            scanf("%d",&num);
            tran (num,2);
            goto loop;
        case 2:
            printf("请输入要转换的十进制数:");
            scanf("%d",&num);
            tran (num,8);
            goto loop;
        case 3:
            printf("请输入要转换的十进制数:");
            scanf("%d",&num);
            tran (num,16);
            goto loop;
        case 0:break;
        default :
            printf("输入有误!请重新输入!\n");
            goto loop;
        }
}
提供给你看看  不知道对你有没有用

8 楼

数组定义的栈
#include <iostream.h>
#include <string.h>
const int maxstrac=10;
class Stack
{
public:
    Stack();
    bool empty()const;
    Error_code pop();
    Error_code top(Stack_entry&item)const;
    Error_code push(const Stack_entry&item);

private:
    int count;
    Stack_entry[maxstack];
};

Error_code Stack::push(const Stack_entry&item)
{
     Errorr_code outcome=success;
     if(count>=maxstack)
         outcome=overflow;
     else
         entry[count++]=item;
     return outcome;
}

Error_code Stack::pop()
{
    Error_code outcome=success;
    if(count==0)
        outcome=underflow;
    else --count;
    return outcome;
}

Error_code Stack::top(Stack_code&&item) const
{
    Error_code outcome=success;
    if(count==0)
        outcome=uderflow;
    else
        item=entry[count-1];
    return outcome;
}

bool Srack::empty()const
{
    bool outcome=ture;
    if(count>0)
        outcome=false;
    return outcome;
}

Stack::Stack()
{
    count=0;
}

9 楼

链表定义的栈
struct node{
    node_entry entry;
    node *next;
    node();
    node(node_entry item,node *add_on=NULL);
};
node::node()
{
    next=NULL;
}
node::node(node_entry item,node *add_on)
{
    entry=item;
    next=add_on;
}
class stack{
public:
    stack();
    bool empty()const;
    error_code push(const stack_entry &item);
    error_code pop();
    error_code top(stack_entry &item)const;
    ~stack();
    stack(const stack &original);
    void operator=(const stack &original);
protected:
    node *top_node;
};
error_code stack::push (const stack_entry &item)
{
    node *new_top=new node(item,top_node);
    if(new_top==null)return overflow;
    top_node=new_top;
    return success;
}
error_code stack::top(stack_entry &item)
{
    if(top_node==NULL)
        return underflow;
    item=top_node->entry;
}
error_code stack::pop()
{
    node *old_top=top_node;
    if(top_node==null)return underflow;
    top_node=old_top->next;
    delete old_top;
    return success;
}
stack::~stack()
{
    while(!empty())
        pop();
}
void stack::operator = (const stack &original)
{
    node *new_top,*new_copy,*original_node=original.top_node;
    if(original_node==null)new_top=null;
    else{
        new_copy=new_top=new node(original_node->entry);
        while(original_node->next!=null){
            original_node->next=new node(original_node->entry);
            new_copy=new_copy->next;
        }

    }
    while(!empty())
        pop();
    top_node=new_top;
}
stack::stack(const stack &original)
{
    node*new_copy,*original_node=original.top_node;
    if(original_node==null)top_node=null;
    else{
        top_node=new_copy=new node(original_node->emtry);
        while(original_node->next!=null){
            original_node=original_node->next;
            nwe_copy->next=new node(original_node->entry);
            new_copy=new_copy->next;
        }
    }
}

10 楼

不要把栈说得那么玄乎……
不就是FILO    LIFO原则嘛,
数据结构可以用数组来实现:
void print2(int n,int k){
    int arr[100];
    int i=0;
    while(n>k&&i<100){
        arr[++i]=n%k;
        n/=k;
    }
    arr[++i]=n;

    for(;i>0;printf("%d",arr[i]),i--);
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册