八皇后
#include<stdio.h>
int a[9]={0};
int count = 0;
int check_position(int i,int j)//判断i行j位置是否为有效位置
{
int m;
for(m=1;m<i;m++)
{
if(a[m]==j)
return 0;
else if((m+a[m])==(i+j))
return 0;
else if((a[m]-m)==(j-i))
return 0;
}
return 1;
}
void print(int a[])
{
int i=1,j;
printf("0 1 2 3 4 5 6 7 8\n");
for(i=1;i<9;i++)
{
printf("%d ",i);
for(j=1;j<a[i];j++)
printf(" ");
printf("* ");
for(j=a[i]+1;j<9;j++)
printf(" ");
printf("\n");
}
printf("==========================================================\n");
}
void queen(int i)
{
int j;
for(j=1;j<=8;j++)
{
if(check_position(i,j)!=0)
{
a[i]=j;
if(8==i)
{
print(a);
a[i]=0;
count++;
return;
/*if(8==i) { print(a,9); return ; }*/
}
queen(i+1);
a[i]=0;
}
}
}
int main()
{
int i;
//for(i=1;i<9;i++)
queen(1);
printf("%d\n",count);
return 0;
}
背包问题
#include<stdio.h>
int w[]={0,3,4,5};
int p[]={0,4,5,6};
int c[4][11]={0};
int main()
{
int tmp=0,i,j;
for(i=1;i<4;i++)
{
for(j=1;j<11;j++)
{
if(j<w[i])
c[i][j]=c[i-1][j];
else if(c[i-1][j-w[i]]+p[i]>c[i-1][j])
c[i][j]=c[i-1][j-w[i]]+p[i];
else
c[i][j]=c[i-1][j];
}
}
return 0;
}
反转链表
#include<stdio.h>
#define MAX 100
typedef struct
{
int v;
int pre;
}s;
s dp[MAX];
int main()
{
int N;
int a[MAX]={0};
s dp[MAX];
scanf("%d",&N);
int i=0;
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
dp[i].v=1;
dp[i].pre=-1;
}
int j=0;
for(i=0;i<N;i++)
for(j=0;j<i;j++)
{
if(a[j]<a[i]&&(dp[j].v+1)>dp[i].v)
{
dp[i].v=dp[j].v+1;
dp[i].pre = j;
}
}
s* tmp=&dp[0];
for(i=0;i<N;i++)
{
if(tmp->v<dp[i].v)
{
tmp=&dp[i];
}
}
printf("%d\n",tmp->v);
printf("%d ",a[--i]);
while(tmp->pre!=-1)
{
printf("%d ",a[tmp->pre]);
tmp = &dp[tmp->pre];
}
return 0;
}