信息学竞赛典型例题程序汇集.doc

信息学竞赛复习 斐波拉契数列（1000000以内的数字） #include “stdio.h” #include “stdlib.h” void main() { long fib1=1,fib2=1,fib=0; printf(1000000以内的数字:\n\n); printf(%d\n%d\n,fib1,fib2); while (fib1000000) { fib=fib1+fib2; fib1=fib2; fib2=fib; printf( %d \n, fib); } system(pause); } 约瑟夫问题 约瑟夫问题_数组 #include stdio.h #include stdlib.h #define Length 100 void main() { int i,j; int len; //输入的总节点数 int n,m; //输入的每次数几个 int remain; //剩下的节点数 int current; //当前数到那个数字 int a[Length]; for(i=0;iLength;i++) { a[i]=1; } printf(请输入约瑟夫问题节点总数：); len=41; //scanf(%d,len); printf(请输入每次数的节点数字：); n=3; //scanf(%d,n); remain=len; //剩下的节点数 current=0; //当前数到那个数字 m=0; //计数到n，m=n时清零 //从1开始数 //循环到剩下的节点数为0 printf(出列的节点的编号依次为：); while(remain0) { current++; while(currentlen) { current-=len; } if(a[current]==1) { m++; if(m==n) { a[current]=0; remain--; printf(%d, ,current); m=0; } } } system(pause); } 约瑟夫问题_数组环 #include stdio.h #include stdlib.h void main() { int a[100]; int i,len,n; //i循环 len总数 n每次数几个 int cur,m,remain; //cur当前是哪个 m 计数 remain 剩下几个 //int t1,t2; for(i=0;i100;i++) { a[i]=i+1; } printf(请输入约瑟夫问题节点总数：); len=41; //scanf(%d,len); printf(请输入每次数的节点数字：); n=3; //scanf(%d,n); a[len]=1; //首尾相连 remain=len; //开始前，剩余数为总数 cur=1; //当前从第1个开始 m=1; //计数从1开始 while(remain0) { cur=a[cur]; m++; if(m==n-1) { printf(%d, ,a[cur]); //t1=a[cur]; //t2=a[a[cur]]; a[cur]=a[a[cur]]; remain--; m=0; } } system(pause); } 约瑟夫问题_链表 #include stdio.h #include stdlib.h struct people { int num; struct people *next; }; typedef struct people node; node *create(int m) { int i; node *h,*p1,*p2; h=p1=p2=(node *)malloc(sizeof(node)); h-num=1; for(i=1;im;i++) { p1=(node *)malloc(sizeof(node)); p2-next=p1; p1-num=i+1; p2=p1; } p1-next=h; return h; } node *findout(node *tp,int n) { int i; node *p; p=tp; for(i=1;in-1;i++) { p=p-next; } return p; } node *moveaway(node *tp) { node