1.
元素a, b, c, d顺序入栈，请写出出栈时的所有可能的顺序和按栈操作不可能出现的序列。
应该有14种情况()
a第一个出栈：abcd; acbd; acdb; abdc; adcb;
a第二个出栈：bacd; badc;
a第三个出栈：cbad; bcad;
a第四个出栈：bcda; cbda; cdba; bdca; dcba;
不可能出现的序列：
adbc; cabd; cadb; dacb; dabc;
cdab; dcab; bdac; dbac; dbca;
通过归纳法可以得出的是n个数依次出栈的出栈顺序满足
在这里插入图片描述
这个实际上是卡特兰数（Catalan number）卡塔兰数的通项公式为
2.
编写算法，用两个大小相同的栈来模拟一个队列的操作(包括入队操作和出队操作两个算法) 。
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT //存储空间分配增量
typedef struct{
int *base; //栈底
int *top; //栈顶
int stacksize;
}stack;
//构造一个空栈
int initStack(stack *s){
s->base = (int*)malloc(sizeof(int)*STACK_INIT_SIZE);
if(s->base == NULL){
printf("Memory allocate failed!\n");
return -1;
}
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
return 1;
}
//压栈的方法，i为需要压入栈顶的元素
int push(stack *s, int i){
//判断栈容量是否已经满了，如果已满，重新分配存储空间
if(s->top - s->base >= s->stacksize){
s->base = (int*)realloc(s->base, (s->stacksize+STACK_INIT_SIZE)*sizeof(int));
}
if(s->base == NULL){
printf("Memory allocate failed!\n");
return -1;
}
*s->top++ = i; //把元素压入
return 1;
}
//弹栈的方法
int pop(stack *s){
if(s->base == s->top)
return -1;
return *--s->top;
}
int main(){
int i;
stack st1, st2;
initStack(&st1);
initStack(&st2);
//假设传入的队列为1,2,3,4,5,6
//则出栈的队列顺序为1,2,3,4,5,6
printf("Enter list is :\n");
for(i = 0; i < 7; i++){
push(&st1, i);
printf("%d ", i);
}
printf("\n");
//出栈的时候每次先把1栈中除栈顶元素之外的所有元素弹到2栈中
//然后在弹出1栈栈底元素
//最后再把2栈中的元素压入1栈中
//重复以上动作，直到1栈为空
printf("Exit the list is: ");
while(st1.base != st1.top){
while((st1.top - st1.base) > 1){
push(&st2, pop(&st1));
}
printf("%d ", pop(&st1));
while((st2.top - st2.base) > 0){
push(&st1, pop(&st2));
}
}
printf("\n");
return 0;
}
在这里插入图片描述
3.
编写一个非递归算法，将十进制数转换成十六进制数，并输出转换后的数。
#include <stdio.h>
int main(){
int i = 0, num, x; //num为输入的十进制数字，x为目标进制类型
int arr[32] = { 0 }; //存放每一次余数的数组
printf("请输入你要转换的十进制数num和转的换的目标进制x：");
scanf("%d %d", &num, &x);
while (num != 0){ //当num不等于0 时进入循环
i++;
arr[i] = num % x;
num = num / x;
if (arr[i] > 9){
arr[i] = 'a' + (arr[i] - 10); //对余数的判断 主要针对16进制
}else{
arr[i] = arr[i] + '0';
}
}
for (int j = i; j > 0; j--){ //倒序输出数组
printf("%c", arr[j]);
}
return 0;
}
在这里插入图片描述
16进制的数主要问题在于大于10的话要用对应的字母来表示，所以多加一条语句，把数字当做对应的字符来存储并打印。
4.
编写一个非递归算法，利用栈计算如下函数的值：
当 n=0时；
当 n>0时。
#include <stdio.h>
#define Maxsize 10 //栈的最大容量，此时n能取的最大值为11
int fun(int n); //函数声明
int main(){
int n = 0;
printf("输入n:", n);
scanf("%d", &n);
printf("计算结果为%d", fun(n));
return 0;
}
//使用栈实现递归操作
int fun(int n){
if (n == 0) return 1;
struct stack{ //定义栈
int no; //n
int val; //pn(x)
}st[Maxsize];
int fv0 = 1; //边界
int top = -1; //初始栈顶
for (int i = n; i > 0; i--){ //将n存入栈
top++;
st[top].no = i;
}
while (top >= 0){ //将Pn(x)存入栈
st[top].val = n*(st[top].no/2); //迭代
fv0 = st[top].val; //迭代，当top=0时，此时no为n，val所存的值即为最终结果
top--;
}
return fv0;
}
递归算法
#include <stdio.h>
int fun(int n);
int main(){
int n;
printf("n = ",n);
scanf("%d",&n);
printf("the result is %d",fun(n));
}
int fun(int n){
if(n==0){
return n+1;
}else{
return n*fun((n/2));
}
}
在这里插入图片描述
网友评论