1.约瑟夫问题:用aLoop来模拟n个猴子,移除的就把数组置零。设置一个整型指针来指向当前数到的数组位置。
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 300
int aLoop[MAX_NUM];
void main()
{
int n,m,i;
int nPtr;
int nCount;
while(1)
{
scanf("%d%d",&n,&m);
if(n==0) break;
for(i=0;i<n;i++) aLoop[i]=i+1;
nPtr=0;
for(i=0;i<n;i++)
{
nCount=0;
while(nCount<m)
{
while(aLoop[nPtr]==0)
nPtr = (nPtr+1)%n;
nCount++;
nPtr = (nPtr+1)%n;
}
nPtr--;//要记得回退一位
if(nPtr<0) nPtr = n-1;//-1之后nPtr有可能是-1
if(i==n-1) printf("%d\n",aLoop[nPtr]);
aLoop[nPtr] = 0;//先输出再置零
}
}
}
2.花生问题:输入一个矩阵之后,首先要找到最大花生的位置,其次计算到新的位置会否超时。注意要看是否在路边。
#include <stdio.h>
#include <stdlib.h>
int Field[55][55];
void main()
{
int M,N,K;
scanf("%d%d%d",&M,&N,&K);
int m,n;
for(m=1;m<=M;m++)
for(n=1;n<=N;n++)
scanf("%d",&Field[m][n]);
int nPeanuts=0;
int nTime=0;
int nCuri=0,nCurj;
int i,j;
while(nTime<K)
{
int nMax=0,nMaxi,nMaxj;
for(i=1;i<=M;i++)//找到最大的花生位置
for(j=1;j<=N;j++)
if(nMax<Field[i][j])
{
nMax=Field[i][j];
nMaxi=i;
nMaxj=j;
}
if(nMax==0) break;
if(nCuri==0) nCurj=nMaxj;//在路边的话要移动
nTime += 1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj);
if(nTime>K) break;
nCuri=nMaxi;nCurj=nMaxj;
nPeanuts += Field[nMaxi][nMaxj];
Field[nMaxi][nMaxj]=0;
}
printf("%d\n",nPeanuts);
}
3.显示器:主要就是把每个笔画存到字符串里,然后根据字母和行数来进行输出。
#include <stdio.h>
#include <string.h>
char n1[11]={"- -- -----"};
char n2[11]={"| ||| ||"};
char n3[11]={"||||| |||"};
char n4[11]={" ----- --"};
char n5[11]={"| | | | "};
char n6[11]={"|| |||||||"};
char n7[11]={"- -- -- --"};
void main()
{
int s;
char szNumber[20];
int nDigit[8]={0},i,j,k,nLength;
while(1)
{
scanf("%d%s",&s,szNumber);
if(s==0) break;
nLength=strlen(szNumber);
for(i=0;i<nLength;i++)//检查每个字符//输出所有数字的笔画1
{
nDigit[i]=szNumber[i]-'0';
}
for(i=0;i<nLength;i++)
{
printf(" ");
for(j=0;j<s;j++)//每个字符输出s个笔画
printf("%c",n1[nDigit[i]]);
printf(" ");
}
printf("\n");
for(j=0;j<s;j++)
{
for(i=0;i<nLength;i++)
{
printf("%c",n2[nDigit[i]]);
for(k=0;k<s;k++) printf(" ");
printf("%c",n3[nDigit[i]]);
}
printf("\n");
}
// printf("\n");
for(i=0;i<nLength;i++)
{
printf(" ");
for(j=0;j<s;j++)//每个字符输出s个笔画
printf("%c",n4[nDigit[i]]);
printf(" ");
}
printf("\n");
for(j=0;j<s;j++)
{
for(i=0;i<nLength;i++)
{
printf("%c",n5[nDigit[i]]);
for(k=0;k<s;k++) printf(" ");
printf("%c",n6[nDigit[i]]);
}
printf("\n");
}
//printf("\n");
for(i=0;i<nLength;i++)
{
printf(" ");
for(j=0;j<s;j++)//每个字符输出s个笔画
printf("%c",n7[nDigit[i]]);
printf(" ");
}
}//while
}//main
4.排列问题:
(1)如何找当前排列的下一个排列
以(2147653)为例子,首先找到aj满足aj-1<aj,(4),其次在j-n里面找最小的比aj-1大的数,并且让这个数和aj-1互换位置,(2157643),最后把j-n升序排列(2153467)
(2)判断一下当前的排列是否已经是降序,如果是降序,那么直接输出升序即可。
(3)qsort的用法:qsort(排列数组的起始地址,排列个数,排列元素的内存大小,比较函数)
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 1024
int an[MAX_NUM];
int MyCompare(const void *e1,const void *e2)
{
return *((int*)e1)-*((int*)e2);
}
void main()
{
int M;
int n,k,i,j,tt;
scanf("%d",&M);
while(M--)
{
scanf("%d%d",&n,&k);//输入
for(i=1;i<=n;i++)
scanf("%d",&an[i]);
an[0]=100000;
for(i=0;i<k;i++)//每次循环都找出下一个排列
{
for(j=n;j>=1&&an[j-1]>an[j];j--);
if(j>=1)
{
//找到j到n中比当前j-1大的最小的数
int nMin=an[j];
int nMinIdx = j;
for(tt=j;tt<=n;tt++)
if(an[tt]>an[j-1] && an[tt]<nMin)
{
nMin = an[tt];
nMinIdx = tt;
}
//交换位置
an[nMinIdx]=an[j-1];
an[j-1]=nMin;
qsort(an+j,n-j+1,sizeof(int),MyCompare);//排序
}
else//已经是降序了
{
for(j=1;j<=n;j++)
an[j]=j;
}
}
for(j=1;j<=n;j++)
printf("%d ",an[j]);
printf("\n");
}
}