一个经典算法的解法,觉着挺有意思
一个经典算法的解法,觉得挺有意思
欢迎大家共同探讨,若有什么不好的地方请指出。
转载请注明出处:http://write.blog.csdn.net/postedit/38342149
突然看到CSDN里的一篇帖子,题目内容为:500个小孩围成一圈,从第一个开始报数:1,2,3,1,2,3,1,2,3,……每次报3的小孩退出,问最后剩下的那个小孩,在以前500人里是第几个???
这是个经典问题,大家说一下算法,把代码写下来,加上注释,这样别人才能看的懂
原题目链接:http://bbs.csdn.net/topics/390793174,期中也有好多大神的思想,可以参考。下面只是个人拙见
楼主曾经看过一篇帖子,解决的是相似的问题,然后再结合自己的思想把程序写出来了,最开始的时候想到用数组求解,循环到最后一个小孩时,就在想怎么又回到开始呢,在这个地方想了一会儿。然后自然就想到了用循环链表可以解决这个问题。
废话不说了,直接说思想,我解决这个问题是把这些孩子创建成一个单循环链表,就像实际生活中的样子,手拉着手在做游戏。
1,把孩子总数设为500,当孩子的总数all_Child不为0 时,进行循环。设一个指针指向第一个孩子,这个指针将一直往下走,直到孩子的总数all_Child不等于0为止。
2,设置一个计数变量cnt进行递增,当指针所指向孩子的标记为 1 时就加 1,标记为0时就退出这次循环,指针指向下一个位置;当 (cnt%3==0) 时,就把这个孩子标记设置成0(注意:最开始所有孩子的标记都为1),输出这个小孩的序号,并把小孩总数减 1 ,让指针继续遍历;
3,最后调用一个函数删除刚才建立的单循环链表,释放内存。
表达也许有些问题,直接看源代码也许好理解一些。。。。
程序代码如下:
#include <iostream> using namespace std; #include <cstdlib> //首先创建一个小孩的结构体 typedef struct Child{ int data; //保存每个小孩节点的编号 bool is_In_Circle; //保存每个小孩是否在圆圈中 Child* next; //next指针指向下一个小孩,因为下一个孩子也是小孩 }Child; //创建一个小孩节点 Child* Create_Child(int num){ Child* p = new Child; p->data = num; p->is_In_Circle = true; //标记小孩是否在圆圈中 return p; } //此处只是删除所创建的链表的函数,供main函数调用 void Remove_Child(Child* p){ Child* pCurrent = NULL; Child* pNext = NULL; pCurrent = pNext = p; int count = 0; while(count++ < 500){ pNext = pNext->next; pCurrent->next = NULL; delete pCurrent; pCurrent = pNext; } } int main(){ Child* newHead, *headPtr, *prePtr, *nextPtr, *temPtr; int all_Child = 500; //把将要用的指针全部指向第一个小孩节点 temPtr = prePtr = nextPtr = headPtr = Create_Child(1); //把所有小孩创建成一个 循环链表 for(int i=2; i<= 500; i++){ nextPtr = Create_Child(i); prePtr->next = nextPtr; prePtr = nextPtr; } nextPtr->next = headPtr; //把最后一个小孩的next变量指向头结点,这才创建完这个单循环链表 int cnt = 1; cout << "退出的小孩的顺序为:" << endl; while(all_Child){ temPtr = temPtr->next; if(temPtr->is_In_Circle){ cnt++; } else{ continue; } if(cnt % 3 == 0){ cout << temPtr->data << " "; if(all_Child==1){ cout << endl << endl; cout << "最后剩下的小孩为:"<< temPtr->data << " "; } temPtr->is_In_Circle = false; all_Child--; //小孩总数减1 } } Remove_Child(headPtr); //删除创建的链表,释放内存 return 0; }
欢迎大家共同探讨,若有什么不好的地方请指出。