鱼C论坛

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

猴子问题

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

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

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

x
大家好!6 V9 L3 [5 b' f4 [1 L. i
这几天我在忙着编一个问题,我用了一种方法编出来!
5 ]3 b4 h; p  k3 \( T* w但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!" |( A3 Z7 p; Q3 _; L3 S' D
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
1 N7 v, t  r# t
7 P# G3 n# Z' K6 s2 E  H7 T. J7 R- Q
                            题目- n: Z5 I. Q' I; ~
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
% ]& t0 h' i3 M) w9 P! k; T8 w' B1 t( U第一种方法:利用循环链表" j: b0 C5 E( I2 }7 Z
#include<stdio.h>3 z3 V# E1 h! @. E' A
#include<malloc.h># G8 A# D, B0 j5 A1 P1 S
#define M 8            //共有8只猴子
5 L2 g- J6 C, i" p#define N 3            //数到3只时退出第三只* Y- K& d. P, Q% L/ O. Y: ^  ?
typedef struct monkey
) d+ _  h+ {4 h* w{int number;
5 Y5 O4 V: s) S% c8 g9 m+ ~int flag;
& e+ J& m& {* Wstruct monkey* next;- z( ]: Q: b  L" k' q, N
}MONKEY;
6 q. V+ T) o9 [$ s' J; x2 V4 @+ Gmain()' x! J$ y. Y8 o7 r; Q+ C" v# ]
{ MONKEY *head=NULL,*p,*s;
9 s% h- a$ P: Y9 Z" F  int i,sum=0,count=0;
' R" M3 `3 y/ ~) N! j  clrscr();              //清屏
+ a) j. _# C# y6 p  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
8 M' V* l  w- I1 o. p+ D) o  p->number=1;p->flag=1;* L7 r9 A2 S" J5 _/ M6 O7 M) V/ h
  p->next=head;
9 n$ i6 r2 @6 g3 E0 k- S  head=p;) j6 N+ Z' H) j4 n
  for(i=2;i<=M;i++)( S" c: b! n, F, o
    { s=(MONKEY *)malloc(sizeof(MONKEY));
" E- z' n5 h  ]8 e6 {' B     s->number=i;s->flag=1;: o5 l- s; l1 N# @( x- ~
     s->next=head;
" S! j; |# [3 b2 y4 e     p->next=s;p=p->next;
$ b" |" w& U, F+ ?5 j2 H3 F    }6 ^6 r& ?  [( J: c7 h9 X7 W  {
    p=head;
2 K; x& p. g4 X6 m* ]$ }3 e0 U   for(;;)
7 z0 H" p/ [! |9 u' l: X    {if(p->flag==1)
7 l1 d1 N) v( P! E. [: U+ Y' ~# c       count++;
  l, }3 n8 J6 b6 J2 e7 a- G     if(count==N), l/ c3 s9 ^2 e4 Q! D' I8 p/ |
        {p->flag=0;. b9 E! r; O( t& M0 |+ W. S8 j3 F6 z
         count=0;, c2 d0 d0 R  B
         sum++;}
! {' N  F1 E8 n: q9 M+ S! ]     if(sum==M-1)
; `% y2 R8 x; @& o3 ^* R        break;8 f8 J+ Q$ o, V% e: z$ U/ b
     p=p->next;0 q! @1 m+ F6 K3 l" b
    }
. h3 d, R  D# G; I" H* c    p=
# P. f; d- f, t    head;5 @( i1 m4 R" D5 Z
    for(i=1;i<=M;i++)
! x( g* T9 j: ]* F* a    { if(p->flag==1)6 J. M- }$ X" K2 s; r1 D4 Q
        printf("\t%d",p->number);) f& v) Y: Z. c
      p=p->next;
2 C( \' V1 K* A+ O7 X    }
4 l( [( c8 O. @9 l. A! {$ Q, t' B) `

2 X9 x3 M8 f, w! n  D* z+ b6 A, f
% M4 R8 ]- c. L$ b- s}

6 y: U2 m4 A/ m1 G2 X第二种方法:数组# @) L& j" \7 X0 i4 c0 B
#include<stdio.h>
! T/ v# L  R3 }* m. B#define M 8
' `0 E% Z. Z/ Z2 R! q  Istruct monkey' ]: ^) C* F; v8 i3 e: \. V  Z6 s
{int number;
% ]. h; e0 v6 O- [) }: b# Bint nextp;
! Q* i9 z! T% l4 V}link[M+1];
. Q) D& O' \+ b3 X2 J; H" Z5 b
5 o  H) Y+ r. w; X5 Bvoid main()
  h; @0 ^+ q" p4 p. m; E{int i,count,h;
8 T8 p; F% y0 C8 }: Ofor(i=1;i<=M;i++)
" b6 {7 \2 J  A! x3 k% I{  if(i==M)
2 s* e) I9 c- J: Y& Z   link[i].nextp=1;7 y. O  {. z) a  P
   else& O  ~" c" |/ X* r- Z, l$ b
   link[i].nextp=i+1;
$ ?1 j. Z. S& f: V0 I  link[i].number=i;" j7 ^! `$ U* f4 \5 e
}+ K- k" I/ k3 F* z/ R# H: n
printf("\n");
# N* q' D0 j+ N3 L! P* ?count=0;+ K/ K! q" S5 w* t- s
h=M;
. X# c- [" M" U3 D, `9 m5 I$ O( `printf("依次退出的猴子: \n");
' a' _! F  ]; c' B+ ^# Xwhile(count<M-1)% m6 z$ a1 _9 `# u" m+ [
{i=0;
/ D" J& w  B. Y, O/ F! swhile(i!=3)
) f) E5 O/ c8 A# {' q% i{ h=link[h].nextp;
& K" J2 Z% |$ ^3 z   if(link[h].number)
" |$ z  p1 C/ J) x- Q     i++;}; @+ d! r7 A0 z; e% {3 B
# f: R4 Q0 G: z9 F+ [: k( q  H
printf("%4d",link[h].number);! q' J1 F) c& t: B9 ~8 E
link[h].number=0;
% G2 n0 y+ K& h6 W, F/ a2 zcount++;* \! f0 a6 ^4 b0 h6 ^6 B
}5 G/ L+ h  Y9 J

4 n, \) T1 e2 ^/ l1 jprintf("\n大王是:");
  ~& N4 }% H+ O! i8 `  for(i=1;i<=M;i++)
9 h1 k; c9 d: M8 M& X( Q# H  if(link[i].number)
# J/ I1 P% V& Y1 a0 x: L! o" y1 c    printf("%3d\n",link[i].number);
, y; _& x2 e# p, Q$ `9 V# |% x5 ?* E
1 L6 O8 I2 u4 _# _! _( Z: ^
}

9 t1 r0 f4 M6 x! Q' e0 X第三种是普通方法for循环

, a' w( @; D0 G* x% `#include<stdio.h>6 h- Y1 N$ z$ u$ @( F  A
void main()
/ @3 x* O4 [* ^# r% d{ int i,k,m,n,num[50],q,*p;% l  g& r+ @1 o+ q
    clrscr();8 M1 I3 E/ ~1 B& D; e
   printf("input number of person: n=");
6 ]" J; f- i# [, v/ x+ \2 O  }1 h" K    scanf("%d",&n);
. W" A* V4 d3 T+ H! _, u0 m6 iprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: v8 `, q, ~0 x5 [
    scanf("%d",&q);
0 Q8 b1 A! J& s( s1 e+ ^   p=num;
# \' C& f) p7 b+ k! M& ]  for(i=0;i<n;i++)
& K( O9 H1 X) z# ~2 W' ?9 @7 y' l    *(p+i)=i+1;7 x7 }$ G8 U2 H- N7 J
   i=0;
: n# h( c; e4 i  \4 a+ Z% }   k=0;
6 F. Z0 e$ P' B7 d   m=0;
6 L0 V, z$ h$ g  z7 |: V  while(m<n-1)
1 _. g; ~: M; c+ x   {if(*(p+i)!=0) k++;4 M1 F: `: e0 @% |
     if(k==q)
5 @" Y% L" ]% ]/ O0 F) R3 |      { *(p+i)=0;- d4 F, ~: a2 _' w
        k=0;  g, @8 S' u$ {' h4 m
        m++;3 w! Q8 F! f8 ?# r
      }" [/ s  \: X/ @& F2 R; h
    i++;/ Y/ T' i" B, B/ N% N) F
    if(i==n)i=0;1 Z  S0 [8 m* T) l& J
   }: n: j* g9 A. L+ z
  while(*p==0)p++;$ F8 Q: Z" c5 D$ }; t9 t2 A- x
    printf("The last one is NO:%d\n",*p);: n) D  d/ j& O* ~) j# h
     getch();! |" M, z. W; o' m4 V9 |
9 l3 J; Q" T& }" B8 U+ C& x: W
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
8 L- i* o8 C' H" D4 X1 H3 anamespace 又费马达又费电
% N, [# M) Y% B; F% @/ A9 o% w{! `, J" j) D' J' @4 f' `
    class Program
0 d/ ^& Y* b0 `6 p* B3 B    {, f; n# S- T8 m4 _7 D
        static void Main(string[] args); b0 O' O1 F5 x3 S! T1 l
        {
5 H& z# R8 v/ x4 [- l9 r            int m, n;
+ B) i( L& ~/ @            Console.WriteLine("请输入数组长度");+ A2 }2 B5 g( A- @  q# o
            m = int.Parse(Console.ReadLine());//m为数组的大小
' X9 y) P' }# Z: W# ~7 h; v" c! H            Console.WriteLine("请输入要截取数字的大小");
( V1 g+ \- e1 e            n = int.Parse(Console.ReadLine());
: h% u. W1 X5 N            int [] numw=new int
4 E% p, @- \8 C& U
/ W  ^3 ]4 @' e&shy;&shy;&shy;;0 C% r% H8 p6 X" q. Y* ~9 d
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数. `9 e; y- y6 O/ j
            {' s% v: m! W: g
                numw[j - 1] = j;& E* K& m0 h, W2 L; f& m0 n# ]+ q4 A
            }( I- k! Y6 O% z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!5 U. I+ i  S7 l  f" L, X
            while (d != m - 1)
  ~/ J6 `, N5 E) t2 ?& J            {
: W) ?/ E1 I- q. s                if (i == m && d != m - 1)
" S& Q1 i1 r: J+ F) l8 h                {! E4 Y2 |' l; h
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!, m3 E5 Y+ s6 D
                    continue;% D3 n* r0 N: {/ m3 @& @  t' o
                }
; V! y7 R/ H# T2 }. z                else
+ U6 _0 d) I/ o2 x: ]* F                {. |- }$ A, b( A5 s6 d
                    if (numw[i] != 0)$ Y1 E( u! r8 \8 b  q
                    {
: ?# w* O2 E& J6 Q& G& |2 ~0 r                        i++;7 I9 h. v+ i# q3 n3 z9 u* x7 r/ v4 w3 M! N
                        k++;- T7 S& C& T; c# Q3 A
                        if (k == n)
6 I0 `' x! I# Q& I/ `" j" B7 ?                        {  y2 A8 U5 L6 U' c) K
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# h$ d  O1 R4 |. N$ B" ?3 }" E% b                            k = 0;! o8 f1 E# o5 }. T0 e
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1$ e9 P3 ^) v  n* H4 |
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 M7 l6 z3 A  C; b4 z9 Q6 I
                        }
. R$ Q  p6 y+ Q5 M5 S3 k7 ^                        else//输出暂时还没有改变数组元素的值
# L2 S6 P3 G2 h) P# ^, W/ o7 ^5 s9 k% a                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 _! ?$ n5 Z; d! b- x
                    }' ?) [& A! a; Y
                    else) Y6 B# [! G+ d) @( F# r# V
                        i++;//数组元素为0,直接跳过,不计数。。。
+ i! o; e, M, V- A) `6 B6 c4 a9 \                }$ N2 r2 _1 i! Z8 n% e) X1 x8 G! A! p

7 s# R4 |. K- t7 p( ^
0 r8 W; L4 M; n) P. N9 ~; p9 q            }//结束while循环' N+ F; R  v9 C; _& r6 l9 u# B
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦& Z/ z# |: d$ a9 O
           
! x/ j# E/ b, E5 b% O                if (numw[i] != 0)# I1 Y% T9 F6 Y  n. V: W& v) z
                    Console.WriteLine(numw[i]);
4 P4 t% v4 j& v! y4 y+ @           
! g" \. o4 H) V$ I2 u            Console.ReadLine();
$ j* g2 @, \" o        }+ |  {" \2 ^% i# C+ b8 H' w) K( h
    }) X/ f- F1 l% E* V: V
}- R* h6 [( b/ k2 }1 w1 B3 v
小甲鱼最新课程 -> 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-1-19 19:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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