posts - 33,  comments - 70,  trackbacks - 0
          問題:約瑟夫環(huán)
          ?有編號(hào)從1到N的N個(gè)人坐成一圈報(bào)數(shù),報(bào)到M的人出局,下一位再從1開始,
          ?如此持續(xù),直止剩下一位為止,報(bào)告此人的編號(hào)X。輸入N,M,求出X。

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

          java實(shí)現(xiàn):
          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實(shí)現(xiàn):

          #include?<stdio.h>
          struct?node
          {
          ??
          int?v;
          ??struct?node?
          *next;
          }
          *p,*head,h;?//head是頭指針,h是頭結(jié)點(diǎn)

          main()
          {
          ??
          int?n,m;
          ??
          int?i;
          ??puts(
          "請(qǐng)輸入人數(shù)n和報(bào)數(shù)上限m?:");
          ??scanf(
          "%d%d",&n,&m);

          ??h.next
          =NULL;?//頭結(jié)點(diǎn)的next為空
          ??head=&h;?????//頭指針指向頭結(jié)點(diǎn)
          ??p=head;??????//p也指向頭結(jié)點(diǎn)

          ??
          /*下面的循環(huán)用來建立循環(huán)鏈表*/
          ??
          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指向第一個(gè)結(jié)點(diǎn)
          ??m%=n;//當(dāng)m>n時(shí)有用
          ??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) 評(píng)論(19)  編輯  收藏

          FeedBack:
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2006-10-15 10:36 | shaoshuai
          挺好挺好  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2006-10-16 00:00 | doyphine
          你的程序有點(diǎn)問題,有待解決喲!!你自己代幾個(gè)數(shù)進(jìn)去看看就知道了,我只試了C的  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2006-10-16 19:43 | 有點(diǎn)傻
          看不懂哦~  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2006-10-17 11:30 | 榆錢
          你的程序的密碼好像就是剛開始排列時(shí)每個(gè)人的序號(hào),是嗎??而且你的輸出有問題,挺大的問題  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2006-10-17 11:39 | hellboys
          java的測(cè)試過,沒問題。 c的只作參考(未測(cè)試過)。  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2006-10-23 22:24 | tian
          very good Thank you very much.  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)[未登錄]
          2008-01-20 14:15 | hhh
          我也覺得,雖然不同的語言,但算法流程應(yīng)該相同。可是你的呢,兩種語言都不一樣~~~  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2008-03-27 21:06 | 22
          根本就不對(duì)
          C語言的!  回復(fù)  更多評(píng)論
            
          # 約瑟夫環(huán)算法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];
          }  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2008-10-30 17:32 | dove52208@126.com
          呵呵 在#include <stdio.h>
          后加上#include <stdlib.h>之后 C的就可以實(shí)現(xiàn)了!!  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2009-02-01 17:56 | johnpzd
          原文思路很經(jīng)典,佩服!!!  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2009-07-17 11:47 | s
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2009-07-17 11:47 | s
          ddddddddddddddddddddd  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2009-10-10 23:01 | 冷如冰
          C語言描述的不是很準(zhǔn)確
          如果n = 10,m = 3,則程序的輸出可能就會(huì)出現(xiàn)問題。  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2009-10-29 21:46 | wx
          挺好的,c的漏粘include<stdlib.h>,因?yàn)橛杏玫絤alloc函數(shù)。  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2010-03-17 11:39 | teamoGod
          其他的沒問題,只有當(dāng)m=1的時(shí)候不對(duì)。  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2010-06-09 21:03 | huchuhan
          哥們啥是鏈表?  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)[未登錄]
          2011-09-12 16:54 | Sky
          @huchuhan
          看不懂
          !  回復(fù)  更多評(píng)論
            
          # re: 約瑟夫環(huán)算法(循環(huán)鏈表解決)
          2012-03-19 10:28 | 527055685@qq.com
          約瑟夫環(huán)的變體-37個(gè)奴隸問題,我也用了循環(huán)鏈表去做
          #include <stdio.h>
          #include <stdlib.h>
          #define MAX 111 //總的奴隸數(shù)
          #define DIE 3 //數(shù)K個(gè),第K個(gè)要被殺
          typedef struct link{
          int value; //用了保存奴隸的編號(hào)
          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; /*將最后一個(gè)奴隸指向第一個(gè)奴隸,最終在這里形成一個(gè)循環(huán)鏈表 */
          slave=head;
          fun(slave);
          return 0;
          }
          void fun(struct link *slave)
          {
          int j;
          struct link* current;
          if(slave->value==slave->next->value)
          printf("這個(gè)編號(hào)為%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);
          }
          }  回復(fù)  更多評(píng)論
            

          只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


          網(wǎng)站導(dǎo)航:
           
          <2011年9月>
          28293031123
          45678910
          11121314151617
          18192021222324
          2526272829301
          2345678

          常用鏈接

          隨筆分類

          隨筆檔案

          文章檔案

          相冊(cè)

          連接

          最新隨筆

          搜索

          •  

          最新評(píng)論

          閱讀排行榜

          評(píng)論排行榜

          主站蜘蛛池模板: 莱芜市| 吉隆县| 松阳县| 盈江县| 集安市| 招远市| 隆回县| 兴业县| 邹平县| 长葛市| 阳曲县| 潼关县| 武夷山市| 西平县| 论坛| 台中县| 福安市| 阳新县| 保德县| 襄樊市| 南宫市| 海阳市| 永平县| 禄劝| 靖宇县| 亳州市| 观塘区| 丰台区| 哈尔滨市| 平湖市| 棋牌| 太谷县| 长泰县| 青阳县| 玛沁县| 榕江县| 西昌市| 德化县| 大宁县| 九龙城区| 永平县|