BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ joee ( 混在北邮) 于 (Sun Jan 4 13:34:10 2009) 提到: 100个人围一圈，从第一个开始，数到第10个出圈，然后从后面重新计数，再到第10个出圈，后面依次一直到所有人都出圈用程序实现，最好有代码 ☆─────────────────────────────────────☆ hg (gyh) 于 (Sun Jan 4 13:44:06 2009) 提到: 不是猴子选大王那道吗? ☆─────────────────────────────────────☆ PtwCJ (鲜的每日C|头像不是我，我是长毛贼~~) 于 (Sun Jan 4 13:45:01 2009) 提到: 最简单最直接的就是直接模拟【在 joee ( 混在北邮) 的大作中提到: 】 : 100个人围一圈，从第一个开始，数到第10个出圈，然后从后面重新计数，再到第10个出圈，后面依次一直到所有人都出圈 : 用程序实现，最好有代码 ☆─────────────────────────────────────☆ derkaiser (剑痞忆秋年|MAEMO|Soton) 于 (Sun Jan 4 14:09:04 2009) 提到: 呃。。。。这题。。。【在 joee ( 混在北邮) 的大作中提到: 】 : 100个人围一圈，从第一个开始，数到第10个出圈，然后从后面重新计数，再到第10个 : 出圈，后面依次一直到所有人都出圈 : 用程序实现，最好有代码 ☆─────────────────────────────────────☆ hg (gyh) 于 (Sun Jan 4 14:10:14 2009) 提到: 大概这样吧 [QUOTE] #include<stdio.h> #include<stdlib.h> typedef struct list { int num; struct list *nextPtr; } node; int main() { int i; int count = 1; int sum = 0; node *headPtr; node *currentPtr = (node *)malloc(sizeof(node)); node *prePtr; currentPtr->nextPtr = NULL; headPtr = currentPtr; for(i = 1; i <= 100; i++) { currentPtr->num = i; if(i == 100) currentPtr->nextPtr = headPtr; else { currentPtr->nextPtr = (node *)malloc(sizeof(node)); currentPtr = currentPtr->nextPtr; } } while(sum < 100) { if(count == 10) { printf("%d ", headPtr->num); prePtr->nextPtr = headPtr->nextPtr; count = 1; sum++; } else { prePtr = headPtr; count++; } headPtr = headPtr->nextPtr; } system("pause"); return 0; } [/QUOTE] ☆─────────────────────────────────────☆ guo (计忆邮心|郭) 于 (Sun Jan 4 14:47:34 2009) 提到: 这不是约瑟夫环么随便baidu一下就有一堆。。。 #include <stdio.h> int josefus(int n,int m) { int l=0,c; for(c=1;c<=n;c++) l=(l+m-1)%c+1; return l; } int main() { int n = 100; int m = 10; printf("%d\n", josefus(n, m)); return 0; } ☆─────────────────────────────────────☆ joee ( 混在北邮) 于 (Sun Jan 4 19:21:34 2009) 提到: 【在 hg 的大作中提到: 】 : 大概这样吧 : [QUOTE] : #include<stdio.h> : ................... [em68] ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Sun Jan 4 19:40:59 2009) 提到: 约瑟夫问题，随便找本数据结构书就是有的【在 joee ( 混在北邮) 的大作中提到: 】 : 100个人围一圈，从第一个开始，数到第10个出圈，然后从后面重新计数，再到第10个出圈，后面依次一直到所有人都出圈 : 用程序实现，最好有代码 ☆─────────────────────────────────────☆ famousz (Fam) 于 (Sun Jan 4 20:19:40 2009) 提到: #include "stdio.h" #include "malloc.h" #include "iostream.h" class CJosephu { private: int * guys; int remain; int total; int m_div; int DoLoop(int PreGuy=0, int PreCount=0) { if(remain==1&&guys[PreGuy]>0) return PreGuy; if(PreGuy==total) DoLoop(0,PreCount); if(guys[PreGuy]==-1) DoLoop(PreGuy+1,PreCount); if(!(++PreCount%m_div)) { guys[PreGuy]=-1; remain--; } DoLoop(PreGuy,PreCount+1); } public: CJosephu(){}; int josephu(int num, int div) { if(num&&div) { remain=total=num; m_div=div; guys=(int*)malloc(num*sizeof(int)); for(int i=0;i<num;i++) guys[i]=i+1; return DoLoop(); } } }; int main() { int num=0,div=0; cout<<"总共几个小孩子？"<<endl; cin>>num; cout<<"数到几的倍数退出？"<<endl; cin>>div; CJosephu j; cout<<"最后剩下的是第"<<j.josephu(num,div)<<endl; getchar(); return 0; } 以做的前面向对象课程的作业 ☆─────────────────────────────────────☆ Evangeline (闇の福音) 于 (Sun Jan 4 20:35:12 2009) 提到: 记得当年数据结构课第一节课的作业就是约瑟夫环。。。 ☆─────────────────────────────────────☆ volCANo (小山|呵呵就叫这个吧『 volcano』) 于 (Sun Jan 4 21:31:10 2009) 提到: 上网查了下算法，重复一遍巩固一下吧设编号为1, 2, .... n - 1, n, 且k = m % n, 则选出第一个人后由f(n)问题变为f(n - 1)问题，编号变为k + 1, k + 2, ... n, 1 , 2, ... k - 2, k - 1（k被选出）则选出前后位置对应关系为： x':1 , 2 , ... n - 1, n x :k + 1, k + 2, ... k - 1, (k被选出) 其中x'为f(n)问题的答案，x为f(n - 1)中问题的答案，根据上面的对应关系，x' = (x + k - 1) % m + 1,得到以下递推关系式子： f(1) = 1; f(n) = (f(n - 1) + m - 1) % n + 1; 则求f(n)的程序为： int f(int n, int m){ int l; int i; l = 1; for(i = 2; i <= n; i++) l = (l + m - 1) % m + 1; return l; } 或者(如果设编号是0到n-1) int f(int n, int m){ int l; int i; l = 0; for(i = 2; i <= n; i++) l = (l + m) % m; return l + 1; } 如果直接模拟的话，算法时间复杂度为O(m*n)，用以上算法则为O(n) 【在 joee 的大作中提到: 】 : 100个人围一圈，从第一个开始，数到第10个出圈，然后从后面重新计数，再到第10个出圈，后面依次一直到所有人都出圈 : 用程序实现，最好有代码 ☆─────────────────────────────────────☆ BismarckDD (豫韵悠悠|以仁为本|〖冰雪猪联盟〗|盟众) 于 (Mon Jan 5 01:46:29 2009) 提到: 这不是约瑟夫问题么？【在 joee ( 混在北邮) 的大作中提到: 】 : 100个人围一圈，从第一个开始，数到第10个出圈，然后从后面重新计数，再到第10个出圈，后面依次一直到所有人都出圈 : 用程序实现，最好有代码

[合集] 问道笔试题