posts - 33,  comments - 70,  trackbacks - 0
          問題:約瑟夫環
          ?有編號從1到N的N個人坐成一圈報數,報到M的人出局,下一位再從1開始,
          ?如此持續,直止剩下一位為止,報告此人的編號X。輸入N,M,求出X。

          約瑟夫環算法(循環鏈表解決).現在老師出的題還是那么....... 呵呵?. 留個念像吧

          java實現:
          public?class?Josephus?{

          ????
          public?static?void?main(String[]?args)?{
          ????????
          if(args.length<2){
          ????????????System.out.println(
          "Input?N?and?M.");
          ????????????
          return;
          ????????}

          ????????
          int?n?=?Integer.parseInt(args[0]);
          ????????
          int?m?=?Integer.parseInt(args[1]);
          ????????
          int?point=0,number=1;
          ????????List
          <Integer>?list?=?new?ArrayList<Integer>();
          ????????
          for(int?i=1;i<=n;?i++){
          ????????????
          //初始化鏈表
          ????????????list.add(i);
          ????????}


          ????????
          while(list.size()>1){
          ????????????
          if(number%m==0){
          ????????????????list.remove(point);
          ????????????????
          --point;
          ????????????}

          ????????????
          ++point;//指針后移
          ????????????++number;
          ????????????
          if(point>list.size()-1){
          ????????????????
          //指針越界重新開始
          ????????????????point=0;
          ????????????}

          ????????}

          ????????

          ????????System.out.println(list.get(
          0));
          ????????
          ????}

          }

          ?

          c實現:

          #include?<stdio.h>
          struct?node
          {
          ??
          int?v;
          ??struct?node?
          *next;
          }
          *p,*head,h;?//head是頭指針,h是頭結點

          main()
          {
          ??
          int?n,m;
          ??
          int?i;
          ??puts(
          "請輸入人數n和報數上限m?:");
          ??scanf(
          "%d%d",&n,&m);

          ??h.next
          =NULL;?//頭結點的next為空
          ??head=&h;?????//頭指針指向頭結點
          ??p=head;??????//p也指向頭結點

          ??
          /*下面的循環用來建立循環鏈表*/
          ??
          for(i=1;i<=n;i++)
          ??
          {
          ????p
          ->next=(struct?node*)malloc(sizeof(struct?node));
          ????p
          =p->next;
          ????p
          ->v=i;
          ????
          if(i!=n)
          ????
          {
          ??????p
          ->next=NULL;
          ????}

          ????
          else
          ????
          {
          ??????p
          ->next=head->next;
          ????}

          ??}


          ??p
          =head;
          ??p
          =p->next;?//p指向第一個結點
          ??m%=n;//當m>n時有用
          ??while(p!=p->next)
          ??
          {
          ????
          for(i=1;i<=m-2;i++)
          ????
          {
          ??????p
          =p->next;
          ????}

          ????printf(
          "%d??",p->next->v);
          ????p
          ->next=p->next->next;
          ????p
          =p->next;
          ??}

          ??printf(
          "%d",p->v);
          }
          posted on 2006-06-07 23:37 地獄男爵(hellboys) 閱讀(13332) 評論(19)  編輯  收藏

          FeedBack:
          # re: 約瑟夫環算法(循環鏈表解決)
          2006-10-15 10:36 | shaoshuai
          挺好挺好  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2006-10-16 00:00 | doyphine
          你的程序有點問題,有待解決喲?。∧阕约捍鷰讉€數進去看看就知道了,我只試了C的  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2006-10-16 19:43 | 有點傻
          看不懂哦~  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2006-10-17 11:30 | 榆錢
          你的程序的密碼好像就是剛開始排列時每個人的序號,是嗎??而且你的輸出有問題,挺大的問題  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2006-10-17 11:39 | hellboys
          java的測試過,沒問題。 c的只作參考(未測試過)。  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2006-10-23 22:24 | tian
          very good Thank you very much.  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)[未登錄]
          2008-01-20 14:15 | hhh
          我也覺得,雖然不同的語言,但算法流程應該相同??墒悄愕哪?,兩種語言都不一樣~~~  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2008-03-27 21:06 | 22
          根本就不對
          C語言的!  回復  更多評論
            
          # 約瑟夫環算法C++
          2008-05-20 17:43 | 呂起民
          enum{N = 10,M=7};
          int main(int argc, char* argv[])
          {
          char array[N] = {1,2,3,4,5,6,7,8,9,10};
          int nCount = N;
          int i = 0;
          while(nCount > 1)
          {
          i = (i+M-1)%nCount;
          printf("%d\n",array[i]);
          memcpy(array+i,array+i+1,nCount-i);
          nCount --;
          // array[nCount] = 0;//可省此行
          }
          printf("約瑟夫=%d\n",array[0]);
          return array[0];
          }  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2008-10-30 17:32 | dove52208@126.com
          呵呵 在#include <stdio.h>
          后加上#include <stdlib.h>之后 C的就可以實現了!!  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2009-02-01 17:56 | johnpzd
          原文思路很經典,佩服!!!  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2009-07-17 11:47 | s
          hh  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2009-07-17 11:47 | s
          ddddddddddddddddddddd  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2009-10-10 23:01 | 冷如冰
          C語言描述的不是很準確
          如果n = 10,m = 3,則程序的輸出可能就會出現問題。  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2009-10-29 21:46 | wx
          挺好的,c的漏粘include<stdlib.h>,因為有用到malloc函數。  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2010-03-17 11:39 | teamoGod
          其他的沒問題,只有當m=1的時候不對。  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2010-06-09 21:03 | huchuhan
          哥們啥是鏈表?  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)[未登錄]
          2011-09-12 16:54 | Sky
          @huchuhan
          看不懂
          !  回復  更多評論
            
          # re: 約瑟夫環算法(循環鏈表解決)
          2012-03-19 10:28 | 527055685@qq.com
          約瑟夫環的變體-37個奴隸問題,我也用了循環鏈表去做
          #include <stdio.h>
          #include <stdlib.h>
          #define MAX 111 //總的奴隸數
          #define DIE 3 //數K個,第K個要被殺
          typedef struct link{
          int value; //用了保存奴隸的編號
          struct link *next;
          }* loop_link;
          void fun(struct link *slave);
          int main(void)
          {
          loop_link slave=NULL,current,head;
          int i;
          for(i=1;i<=MAX;i++)
          {
          current=malloc(sizeof(struct link));
          current->value=i;
          current->next=NULL;
          if(slave==NULL)
          {
          slave=current;
          head=slave;
          }
          else
          {
          slave->next=current;
          slave->next=slave->next;
          slave=slave->next;
          }
          }
          slave->next=head; /*將最后一個奴隸指向第一個奴隸,最終在這里形成一個循環鏈表 */
          slave=head;
          fun(slave);
          return 0;
          }
          void fun(struct link *slave)
          {
          int j;
          struct link* current;
          if(slave->value==slave->next->value)
          printf("這個編號為%d的奴隸不用被殺\n",slave->value);
          else
          {
          for(j=1;j<DIE;j++)
          {
          current=slave;
          slave=slave->next;
          }
          current->next=slave->next;
          current=slave;
          slave=current->next;
          free(current);
          fun(slave);
          }
          }  回復  更多評論
            

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          <2006年6月>
          28293031123
          45678910
          11121314151617
          18192021222324
          2526272829301
          2345678

          常用鏈接

          隨筆分類

          隨筆檔案

          文章檔案

          相冊

          連接

          最新隨筆

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          主站蜘蛛池模板: 策勒县| 万山特区| 修武县| 休宁县| 乡城县| 托里县| 台东市| 浠水县| 阳春市| 星子县| 姜堰市| 五峰| 仪陇县| 永吉县| 大荔县| 沈阳市| 镇原县| 山东省| 庄河市| 耒阳市| 达孜县| 扎鲁特旗| 日照市| 清河县| 砀山县| 罗田县| 肥城市| 禹州市| 新昌县| 肇庆市| 龙门县| 德化县| 沭阳县| 正蓝旗| 西和县| 岳阳市| 西乌珠穆沁旗| 石城县| 巴彦淖尔市| 泾川县| 五莲县|