数据结构----栈与递归例题讲解
（ps：一些需要注意的点和思路都在代码中了）
1.将十进制数字转化为二进制数字然后输出
#include <stdio.h>
void dectobin( int n );
int main()
{
int n;
scanf("%d", &n);
dectobin(n);
return 0;
}
void dectobin( int n )
{
if(n/2)
{
dectobin(n/2);
}
printf("%d",n%2);
}
//错误代码
//输入0，就会导致没有输出
//void dectobin( int n )
//{
// if(n==0)
// return;
// else
// {
// dectobin(n/2);
// if(n%2!=0)
// {
// printf("1");
// }
// else
// {
// printf("0");
// }
// }
//}2.第一行输入元素个数n，第二行输入n个数，用分治法快速求这n个数的最大值和最小值
#include <stdio.h>
#define N 100
int max(int *a,int m,int n);
int min(int *a,int m,int n);
//注意采用分治法，不使用循环语句
int main()
{
int i, n,a[N],max_val,min_val;
scanf ("%d", &n);
for(i=0;i<n;i++)
scanf ("%d", &a[i]);
max_val=max(a,0,n-1);
min_val=min(a,0,n-1);
printf("max=%d,min=%d", max_val,min_val);
return 0;
}
//类似二分法
int max(int *a,int m,int n)
{
int mid;
if(m==n)
return a[m];
else
{
mid=(m+n)/2;
int left=max(a,m,mid);
int right=max(a,mid+1,n);
//一半一半的分开，最后成为前后两半的两个元素相比较
//一层一层选出最大的返回出来然后比较
//最里层只有一个数，把两个最里层的数返回比较
if(left<right)
{
return right;
}
else
{
return left;
}
}
}
int min(int *a,int m,int n)
{
int mid;
if(m==n)
return a[m];
else
{
mid=(m+n)/2;
int left=min(a,m,mid);
int right=min(a,mid+1,n);
//一半一半的分开，最后成为前后两半的两个元素相比较
//一层一层选出最大的返回出来然后比较
//最里层只有一个数，把两个最里层的数返回比较
if(left<right)
{
return left;
}
else
{
return right;
}
}
}3.在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。
#include <stdio.h>
#include <stdlib.h>
#define N 20 //最多皇后个数
int q[N]; //存放各皇后所在的列号,即(i,q[i])为一个皇后位置
void dispasolution(int n) //输出n皇后问题的一个解
{
for (int i=1;i<=n;i++)
printf("(%d,%d)",i,q[i]);
printf("\n");
}
bool place(int i,int j) //测试(i,j)位置能否摆放皇后
{
if (i==1) return true; //第一个皇后总是可以放置
int k=1;
while (k<i) //k=1～i-1是已放置了皇后的行
{ if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)))//因为行是递增的，只需要保证不在一列上并且不在一条对角线上
return false;
k++;
}
return true;
}
void queen(int i,int n);
int main()
{ int n; //n为存放实际皇后个数
scanf("%d",&n);
if (n<=20)
queen(1,n); //放置1～i的皇后
return 0;
}
void queen(int i,int n)
{
if(i>n)//放置完了n个皇后
{
dispasolution(n);
return;
}
else
{
for(int j=1;j<=n;j++)//在每一个i行试探每一个j列
{
if(place(i,j))
{
q[i]=j;//表示这个位置可行
queen(i+1,n);//下一行即下一个皇后//注意不是queen(i+1,j);第二个参数不变，用来当边界条件
//假如j列不可以，就返回到这里，然后进行下一次for循环，试探j+1列是否可行
}
}
}
}4.设a1, a2,…, an是集合{1, 2, …, n}的一个排列，如果i<j且ai>aj，则序偶(ai, aj)称为该排列的一个逆序。例如，2, 3, 1有两个逆序：(3, 1)和(2, 1)。设计算法统计给定排列中含有逆序的个数。
//总体思路：通过排序这一过程来计算存在的逆序数
//可以先看一下这篇文章的讲解有利于理解这个题https://www.cnblogs.com/bigsai/p/12253254.html
#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<malloc.h>
#define N 1000
using namespace std;
int ans=0;
void Merge(int a[],int low,int mid,int high);
void mergesort(int a[],int low,int high);
int main()
{
int a[N],n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
mergesort(a,0,n-1);
cout<<ans;
return 0;
}
void Merge(int a[],int low,int mid,int high)
{
int lindex=low,rindex=mid+1;
int team[high-low+1];
int teamindex=0;
while(lindex<=mid&&rindex<=high)//这里注意每部分的截止条件
{
if(a[lindex]<=a[rindex])
{
team[teamindex++]=a[lindex++];
}
else
{
team[teamindex++]=a[rindex++];
//ans++;//不对
ans+=mid-lindex+1;//加上左侧还剩余的
//为什么只有这个else条件需要加呢
//因为前提是你这两部分已经是有序的了，当lindex<rindex时，
//在左边那部分中lindex小于左边所有的数据，而lindex小于rindex，即小于右边所有的元素，
//所以把他前移不会影响逆序数的数量，因为对lindex来说不存在逆序数
//但当rindex小于lindex时，rindex小于左边所有的元素（小于左边存在逆序数），
//也小于右边所有的元素（小于右边不存在逆序数）
//所以改变的逆序数的数量即为左边所有元素的数量
}
}
//这两个while循环最后只执行一个，因为只有一个走到头了才会结束上面那个循环
while(lindex<=mid)
{
team[teamindex++]=a[lindex++];
}
while(rindex<=high)
{
team[teamindex++]=a[rindex++];
}
for(int i=0;i<teamindex;i++)
{
a[low+i]=team[i];//注意a的下标从哪里开始，因为是一层一层的
}
}
void mergesort(int a[],int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
//这个函数调用顺序是最先两个元素比较排序，在排序的过程中判断有没有逆序数
mergesort(a,low,mid);
mergesort(a,mid+1,high);
Merge(a,low,mid,high);
}
}
5.输入给出正整数n，请编写程序输出前n个正整数的全排列（n<10），此全排列中无重复数字
#include <stdio.h>
int a[15]= {0};
int books[15]= {0}; //用来记录这个数字出现没有
void Print(int a[],int n)
{
for(int i=1; i<=n; i++)
{
printf("%d",a[i]);
}
printf("\n");
}
void go(int a[],int n,int step)
{
if(step>n)
{
Print(a,n);
return;
}
else
{
for(int i=1; i<=n; i++)
{
if(books[i]==0)
{
books[i]=1;
a[step]=i;
go(a,n,step+1);
//只要是走到这里说明step+1步已经完成，i也完成（要及时给books的i归零，不要影响下一轮寻找），
//如果i还能继续取那么a的step步重新赋值i+1，然后往后递归
a[step]=0;//step=i这一步试探结束，再往前（step-1）回溯了
books[i]=0;
}
}
}
}
int main()
{
int n;
scanf("%d",&n);
go(a,n,1);
return 0;
}
6.输入一个数N，将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1<mi+1,则N1序列必定在N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
#include <stdio.h>
int n;
int a[40];
int cnt=0;
void dfs(int num,int location,int sum)//第一个参数为当前因子的大小
{//上一层传进来的是location+1，相当于已经多了一位了，所以循环的时候i<location
if(sum==n)
{
for(int i=1; i<location; i++)
{
if(i==1)
printf("%d=%d",n,a[i]);
else
printf("+%d",a[i]);
}
cnt++;
//这个if条件是||,不是&&
if(cnt%4==0||num==n)//第二个条件表明当只有一个因子时输出回车
printf("\n");
else if(cnt%4!=0)
printf(";");
}
else if(sum<n)
{
for(int j=num; j<=n; j++)
{
a[location]=j;
dfs(j,location+1,sum+j);//第一个参数得是j
a[location]=0;
}
}
else//需要有退出的条件，不能只有上面两个判断条件//否则卡在第一次调用中无法回溯
return;
}
int main()
{
scanf("%d",&n);
dfs(1,1,0);
}