鱼C论坛

 找回密码
 立即注册
查看: 3665|回复: 4

猴子问题

[复制链接]
发表于 2011-10-2 03:45:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
大家好!! }9 R. s% Z. w7 n, A3 c3 L
这几天我在忙着编一个问题,我用了一种方法编出来!; _; v: f8 K3 U
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!) |# W8 V5 X2 Q# c  y
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 ?$ Y  E4 L7 y3 A# x3 G- h: \) z

6 Q! h9 Q; H; @2 D0 m
                            题目8 Q. U9 ~: ~7 }/ \2 ~
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ O( Q3 N0 {3 b+ l5 g, e, j+ f
第一种方法:利用循环链表
/ h$ X4 q2 P# l) }#include<stdio.h>
- \# ?8 E/ h2 {# t) |#include<malloc.h>
7 [. c; K- ]! m2 B#define M 8            //共有8只猴子4 `: ~# u  O. N5 o& R- K
#define N 3            //数到3只时退出第三只% W+ B) ]5 G: K0 Y# Z/ W! b
typedef struct monkey
0 A0 s- w5 H$ Z) @% i) c9 t( X{int number;- p* m; w. L* K
int flag;
8 T/ w+ w& b/ ^8 o5 C0 |' G% N* |" Zstruct monkey* next;
9 n- D7 D$ y" d( y% R}MONKEY;+ `5 B5 D5 c8 Q# H
main(); m+ a" Y. S; F1 o5 h
{ MONKEY *head=NULL,*p,*s;
$ j5 L, M& A) J, J# j  int i,sum=0,count=0;; f) `2 D+ d9 J2 {  H
  clrscr();              //清屏" D4 W) v! l9 j9 e# T2 `) B
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
% y4 J7 H  R% ]  p->number=1;p->flag=1;
$ e9 L0 i. T0 x  p->next=head;/ z- d# Q! P7 `9 y7 z  {
  head=p;
" N5 P+ F: `: a2 ?  for(i=2;i<=M;i++)
9 M' l+ _9 F  f4 `    { s=(MONKEY *)malloc(sizeof(MONKEY));
; ]* ?- h: b& Q8 @  v1 z     s->number=i;s->flag=1;
2 r, u" r* u1 @$ Z, }' W8 q; T     s->next=head;3 n, T7 Z9 }% [- w# z& N# {- f! F" R
     p->next=s;p=p->next;5 q7 @; n# `/ V/ o2 D5 l; q
    }+ m  C9 U" f% D* c) r* Q9 Q# G
    p=head;
; H1 J, f, E+ q2 ~* Q   for(;;)& G4 k4 Z% D/ J
    {if(p->flag==1)
2 R5 f* E. ]4 t/ y2 _: p7 v       count++;% T  b  I) a) A6 J4 V, w
     if(count==N)
0 G  U+ t$ P) k, e( @( [  T1 g6 c        {p->flag=0;
3 g' W- v* K1 e5 ~8 s7 E         count=0;
; J; @8 ~: A2 y: w6 K9 v7 w         sum++;}' x8 |4 D1 R: f
     if(sum==M-1)5 b+ r& X4 E) z/ d/ V
        break;3 _- F! b; Y1 Z5 O% b, n& M
     p=p->next;. u' Q8 q6 R/ [
    }
( u" l0 r1 ~: V% ]1 L- L' }    p=
5 `& t2 ~0 C# j8 U$ ^  \! R" L    head;
8 c4 ?: K1 H* x4 k( m! E3 h    for(i=1;i<=M;i++)
- k2 m8 _9 K. w" ?9 r    { if(p->flag==1)! l6 E1 T' r$ _' f! P- d
        printf("\t%d",p->number);
2 v; ~  z5 l' \( s  b' \      p=p->next;- t+ G( Y' D' n! K
    }0 s' F. e# t$ m, ~+ r  z6 G
; y0 |# J! H; }$ e( W, C. n1 [

' X& h) Y& R% c3 w& t4 g9 ~: l+ V+ ^+ i7 @) B- \8 g% y  c
}
7 S! m! H4 J4 N! u* R; ^* x9 h
第二种方法:数组
% {. w' b8 }4 i) n6 G6 e( k#include<stdio.h># G4 T- J; G3 c
#define M 8# a$ H% [0 p5 l( Z% b
struct monkey
5 f5 H" L% C" {* Q! M2 b+ |" [{int number;
- W- k0 `# O, u6 B* r+ `5 l: qint nextp;2 }# p" E9 y, q4 l) ?! q; r5 h
}link[M+1];+ P/ G1 p$ U3 q, H% g' E1 `

0 b* ?) |0 o$ G9 @7 o- s, [) C# I$ Gvoid main()
% |! G1 V, W1 Z% O. o{int i,count,h;7 Q: h9 M* H7 u( A
for(i=1;i<=M;i++)4 {. e  ~: `. K3 \& @
{  if(i==M)9 }( R! Y% g  T6 T/ ?1 f+ K. g
   link[i].nextp=1;, W. r3 m5 t1 t* x
   else  a5 S- @  D2 V: `
   link[i].nextp=i+1;
& l+ m/ w& H1 q  link[i].number=i;7 W" Y, [' B7 H- E
}
$ ]! M3 d: ]2 o* rprintf("\n");
4 m; n; V' f0 R/ M8 w8 j" Fcount=0;3 B8 d9 ]$ r& l# Q9 B+ _5 c" f
h=M;; d/ R9 Q- f, {- z) q2 A
printf("依次退出的猴子: \n");
8 V& l. u9 m  c( h; {/ rwhile(count<M-1)
' j4 `( n2 c: J9 Q* ?4 d{i=0;
; l: n  F: A9 m# W& _1 H/ \while(i!=3)* i1 ~. O2 }- E! d  E3 B! z
{ h=link[h].nextp;( }0 t% D+ D3 [; g
   if(link[h].number)
0 y9 K" T  A; @! f( {0 q     i++;}7 ~: W  B# Q5 X) ^! l

. n/ x# M( d1 F3 B7 a/ hprintf("%4d",link[h].number);
! s! y; s; Y; P: T9 v$ ~, {, u) clink[h].number=0;
. h0 V; m! Q, {count++;3 q( z3 F$ e  T2 t, O; h. d" ~
}) i9 A6 x' @2 y+ p) h. Y
0 S' Y0 \+ o' c, v$ m9 H. z
printf("\n大王是:");% D* _4 t+ X; h
  for(i=1;i<=M;i++)4 i' q8 ]5 h7 v/ n; b& {" t
  if(link[i].number)
% b2 Y  j! @% B( o    printf("%3d\n",link[i].number);
  j, x/ V5 k0 |0 O1 E+ Q0 `5 S. B: ^3 `$ J
! _, t5 T5 C  q) \) E* \+ H
}
% L' O! L$ O% J
第三种是普通方法for循环
% J9 @4 E  D$ |* l- r; J; Y4 C
#include<stdio.h>2 T6 F4 ]4 [  P& e
void main()
7 j4 M" q+ g$ A' Y' b8 r; S* d( ~- }1 N{ int i,k,m,n,num[50],q,*p;/ e% w4 U8 P' ]. M, J- j
    clrscr();
) k) o( S2 `/ z  o   printf("input number of person: n=");
5 m7 u9 e3 j. Y& C, a+ ^6 R+ M- [    scanf("%d",&n);
& a. z) ]- p! r# ]printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只. O: M1 y! R; r3 |' j( @, [/ D" i
    scanf("%d",&q);: C& R9 {% c( l( @* g  z9 [
   p=num;! O! p* T1 }  c# S& M2 H
  for(i=0;i<n;i++)$ ^% w- U1 G! V
    *(p+i)=i+1;
) u$ c5 m  g' A   i=0;
; h! A: q+ N. `+ G: ?* X- X3 q   k=0;
, Q7 F2 V9 s( Q! l* j  M# U3 a   m=0;6 c3 U/ u6 F' S5 p4 o1 a$ f
  while(m<n-1)
" m+ s$ @# b; M4 M' y; L' R( o   {if(*(p+i)!=0) k++;9 G' j9 Y1 T+ X3 {
     if(k==q)% d4 h( k; f' I1 k" i
      { *(p+i)=0;
; J. S! t+ l& C9 V1 |3 v        k=0;
) {) }3 f& \' E6 ~& G9 q% B        m++;
4 m  k) @3 U3 D3 B+ F      }& Q- A4 y- }- y
    i++;" e& x+ {" q; o; Y7 l- A
    if(i==n)i=0;
: @# s; g3 g0 \, T: D2 _0 [$ g   }# i/ N  ~8 b% ~  o1 \- j) E
  while(*p==0)p++;) Z: k. d, H1 ]
    printf("The last one is NO:%d\n",*p);
9 t0 _6 N. x, u- D9 a     getch();
5 `! P2 E3 ]/ Y( X3 Q+ m) K
( Q3 }5 f3 e- W/ V/ F}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;* [0 b' J$ V" C3 }( o7 H4 k
namespace 又费马达又费电
, S0 b. k5 Y& k1 }# r1 f( e5 h{4 }4 T0 N+ q4 _
    class Program
6 M$ D; C# Y/ a; v3 U. e" |    {
( C- w$ ~6 h6 L) C" |        static void Main(string[] args)
( D  a6 b9 D  I% q( \5 ]        {8 y' Q: c5 j- X
            int m, n;
% s# g+ u: q% y2 f8 \/ O            Console.WriteLine("请输入数组长度");
2 I& g( b3 P7 b2 g& h            m = int.Parse(Console.ReadLine());//m为数组的大小+ r4 x8 E+ {+ L& ~( z
            Console.WriteLine("请输入要截取数字的大小");
- ~- b1 h5 N" q1 a0 X# G$ Z            n = int.Parse(Console.ReadLine());* l  |) r. S( D
            int [] numw=new int
/ l! F' ~, g. ]: b/ Q/ k# z, y3 m
2 N3 G7 \4 m7 I6 ^- L# L0 O&shy;&shy;&shy;;
. ?6 K5 K8 x9 e5 o, d# b+ Z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
7 J. j' f% M! m; E9 L- O0 }0 Q& h            {
7 D" X# F% Y; j% e3 ]$ h' _" \$ w* T                numw[j - 1] = j;* c/ I& ^/ j) G: K  \
            }
" o% b5 e- p  o& T( B  ^            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
7 g7 i" B  J: O1 h            while (d != m - 1)
4 R, F# `9 ]8 i            {
. ?3 O2 H# V  C/ ~                if (i == m && d != m - 1)
6 {) I, i+ T: u& M# u4 `( D( B                {/ K3 F' a' j. Z. u2 Y/ x8 D
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!" z* ?" q3 s9 _: D! [% D
                    continue;! r# H" {; q9 H( t4 [
                }
; W5 [1 o2 }% w7 q, D& D" [5 d, M                else) h9 A( @+ j- k, J) V: B
                {% {: K5 K2 p. f7 Q- {( g# r9 m
                    if (numw[i] != 0)2 v; O; h  R3 }  D  h9 F
                    {
( g7 m1 |5 a; m' x0 ?/ ^                        i++;
8 M3 y) p+ N+ d# |                        k++;2 y  b) H3 u/ i# G
                        if (k == n)
/ m. h. c4 i& i" u2 Y                        {
8 x: A& d7 _+ G  P; B6 k# e* w                            numw[i - 1] = 0;//把在n位置数组元素的值改变了+ W7 D/ A8 l0 }- i% D
                            k = 0;
; ^/ X% @- A* F8 Y0 ~! I$ Q              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
& K3 Q' c" x7 n# r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: |8 {, ^# M% B. o: x7 _/ Y                        }
5 p9 B  ?: a" E( n  N  C                        else//输出暂时还没有改变数组元素的值
2 `" z) ]# P, F                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! m6 K$ L9 Q6 k2 w+ Z4 K/ _                    }
6 C# k9 l  v' u5 D- d                    else
: w- w. z- i8 I: p9 _$ G                        i++;//数组元素为0,直接跳过,不计数。。。
8 \/ V5 b7 W5 Q- o4 _( T& i                }5 H1 X- I2 s* \7 C
- E5 a$ H; O0 Q, N9 q& m
, R  N! ?6 ?  ~' Y' D$ m( M8 P& C
            }//结束while循环; j! f% {! }$ y
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
; Q6 i( q# f  S           5 h7 }6 g1 J/ Z0 P
                if (numw[i] != 0)
+ [- e8 s1 `# E$ ]# n, R- A                    Console.WriteLine(numw[i]);
6 x7 M$ a/ L/ Y. A; B/ G  C           
* g- r& ?' m3 ~* u0 s            Console.ReadLine();
4 d8 ?& i4 k  w1 \0 A$ X9 a: x/ c9 W        }  d  O3 J: ]8 F
    }
- ^; Z8 i: o$ k. C, Z% X}4 A4 [# P/ x( F( l. o- M
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
小甲鱼最新课程 -> https://ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2026-3-29 00:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表