鱼C论坛

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

猴子问题

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

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

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

x
大家好!  s, [0 p" A% d& U& r% d
这几天我在忙着编一个问题,我用了一种方法编出来!
. b! B' E( d+ T: p5 b% r/ q但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
+ d' i' ~, E  H- `$ x$ _: s5 Y/ f注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
$ M4 a, W% N( S9 `* O( ~8 `" ?+ C" e# N
' \: W' M9 C4 k  Z' Y: ~
                            题目
6 l/ _1 j5 x1 u9 ^( E山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。, J6 h: p% P) q6 X6 F
第一种方法:利用循环链表
  M, ~9 P3 W( M% A#include<stdio.h>4 L2 t/ g* N' L$ @8 ~/ J
#include<malloc.h>% \9 m! l3 E0 g. B. B. \
#define M 8            //共有8只猴子
4 d( w" e6 g+ i- c) Y# m8 V2 w#define N 3            //数到3只时退出第三只
" ?+ _0 W/ w7 d! mtypedef struct monkey7 [! }8 F2 y$ d8 h4 r$ q% {
{int number;
7 f& a' T/ @) a+ O3 Zint flag;0 D4 g7 {3 a- J. v) B+ B1 R
struct monkey* next;
) j* X9 S5 j9 B' N( R$ O. u}MONKEY;8 j: j$ o: Y- w
main()9 e* _) e9 u2 _7 ]/ g* B# k* M! J
{ MONKEY *head=NULL,*p,*s;
( G, A% R9 ]4 @  X) `# H2 R$ j  int i,sum=0,count=0;
9 q; e- o% y1 n/ x2 I  clrscr();              //清屏
8 y$ @: V2 @+ Y) y  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. c/ o8 s4 z) X3 `; d: a
  p->number=1;p->flag=1;6 L+ Z: S% D( _5 s, G' a
  p->next=head;
; @/ N5 C/ y& B( C% r  head=p;, _( o4 \& J) ~& k" H
  for(i=2;i<=M;i++)$ y! z+ e* ^4 S9 @! r" U
    { s=(MONKEY *)malloc(sizeof(MONKEY));
0 e4 ]0 n# y% ^) H" O7 W     s->number=i;s->flag=1;
7 S* ^8 f, w  `! V9 v# G     s->next=head;
9 \% N. |- F! k% S     p->next=s;p=p->next;1 u! @) p' B5 G4 R+ @
    }
( F$ A: D4 u/ S! d! y8 l+ T    p=head;
/ z  |! C3 Y+ I/ t   for(;;)
3 K( G- `6 ]' ]; E    {if(p->flag==1). z, _9 A+ M& ]5 b
       count++;0 [& c8 ]6 M+ a8 U3 H. e6 |- n1 m6 y3 j
     if(count==N)4 ?7 A- r! ^$ a+ u" X
        {p->flag=0;' {) c6 d' j5 O) b8 ~
         count=0;
# Q( S- ~3 N% q+ _1 T  ]! F; d/ \         sum++;}* @$ D: A+ Z( T0 T! t2 C
     if(sum==M-1)) u0 m1 \2 ^; @8 j  T  o, U
        break;; ^7 R; b0 f* r
     p=p->next;
2 ~: e3 |  p9 Y7 ?* N8 _3 z    }1 `% m# v4 g  h' G% w
    p=
% k8 n+ s. Z; N    head;# _4 h  g' K1 u; y
    for(i=1;i<=M;i++)
" J6 {0 B1 y7 }# A9 |1 r- S4 }2 U    { if(p->flag==1)
" T$ @7 b; R" ~3 S4 }        printf("\t%d",p->number);+ L7 E3 u! C3 R5 E
      p=p->next;
, x/ |+ A; F! r5 G    }
7 U5 D+ a; l5 O" ?( X, j* e. S( _
; l! Z) ~& o0 k' V: s9 g1 G" _0 k$ c* d  Q

- x) P  J5 G' e- u( O8 F}
' ]+ p: ]- i+ A0 J5 L' r
第二种方法:数组
1 t8 d0 W+ `  d: t- I#include<stdio.h>0 x+ x; ]- i- @2 T4 @
#define M 8
9 l5 g5 W2 N7 t; Tstruct monkey
. e$ M0 ^1 T" j; [+ m{int number;; n+ X, v7 Y6 W7 I  L
int nextp;7 T( r" Y: I5 T& u% n
}link[M+1];
" P  W, Y7 I% y
! Q; x, s+ b$ e- p- H4 kvoid main()
/ z0 G/ j6 c7 Z# |{int i,count,h;/ N4 _( m6 q0 J0 }# B5 B& V9 @; u8 R$ P
for(i=1;i<=M;i++)
+ O/ w1 P6 V0 h7 H6 t( I{  if(i==M)
1 R" w  v  C+ R# G4 g   link[i].nextp=1;
* u/ v3 A/ A& `( p   else5 N  O8 c( V6 R6 k, }
   link[i].nextp=i+1;5 {, H1 [. s/ O) V7 D3 |5 X
  link[i].number=i;
( R% r! F# i; E2 b8 T4 p}0 y/ l* ?8 u9 N2 S4 c8 S6 K
printf("\n");( i0 E8 k; _2 H1 J! d, d
count=0;# ?) T; W( o0 p6 W5 g
h=M;# d+ a! X9 N( F( @3 u: z
printf("依次退出的猴子: \n");
; |. c/ W& \. A# o4 }& wwhile(count<M-1)# d% ~  N6 j4 [& k! L7 r
{i=0;
' s/ E( z$ V4 m# L5 v7 Rwhile(i!=3)
" G4 z' H& Y4 H{ h=link[h].nextp;
! A/ R. u  ?4 ?& [8 f. [   if(link[h].number)$ k5 L) I6 R* ~: a
     i++;}0 K7 U# Q. s& m: X* D# I5 m) O
5 s2 S- x6 S# I, F( k( {
printf("%4d",link[h].number);
# l3 x/ z! h$ k5 q4 J+ d5 c, Y2 elink[h].number=0;2 J. R6 z) ]2 D: O9 X
count++;6 n4 d( e% a9 L  O8 V4 l
}9 X9 y8 g# q! J- B: [, B$ }
, f4 q/ m) J: ?6 c0 u& b
printf("\n大王是:");
, t: v; h& Q4 ~2 x0 M  for(i=1;i<=M;i++)
& M% J8 n2 }+ c) p5 |  if(link[i].number)7 t' Q8 E4 Z- I7 R: ?
    printf("%3d\n",link[i].number);/ k3 B' @4 }/ n: b& x8 M

. C, C1 J3 e6 T5 o, X* L5 q9 w1 ?  E; ^
}

) Q2 Q3 c( C( m5 r$ j第三种是普通方法for循环
( u: [; }  [$ P" z
#include<stdio.h>" z* n0 s. m8 [: B8 F5 b" m" P5 u
void main()
% [5 T; S8 e: c6 O  y{ int i,k,m,n,num[50],q,*p;" d9 O  v& X$ ?. S. E0 Q' [- y) H
    clrscr();
* o7 }7 L3 w) |   printf("input number of person: n=");
9 y' V& G& i' a8 E- I    scanf("%d",&n);
, n9 p1 U' s% ]! u. A! B& x0 q# X* `printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
! q( x; x, ^1 M6 O/ L    scanf("%d",&q);
7 J& e& B3 w+ e2 g. T1 [5 }   p=num;
0 V- s& Y8 _* v+ C' e  for(i=0;i<n;i++)
" z. P6 u8 l9 q( [- i1 j    *(p+i)=i+1;% {! K5 M- J% Z7 F
   i=0;4 z0 _5 M) x2 J1 Z% L
   k=0;
; f. |; U* {6 I9 L   m=0;
/ D2 O6 p1 Q! ~6 a2 y  while(m<n-1)
6 ~! J2 @  b  ?! c3 S; H   {if(*(p+i)!=0) k++;6 Q: ~$ Q4 T& A9 T
     if(k==q)
6 R' {: G5 J  m7 [/ ^      { *(p+i)=0;
) C3 J' W+ U# @# t' x) |, H        k=0;
4 W$ B! o1 L& T% v$ t& [        m++;3 p7 R/ O' l: u7 a  d0 f9 k
      }/ K' w$ t0 U. n' ]' \8 U. \
    i++;
6 Y8 r: y5 n  G4 J% u4 u% Y8 X    if(i==n)i=0;: L' Y- L* w# ~( _* Z
   }
. a1 j" \$ @6 [* m) \8 F; I  while(*p==0)p++;
' P, w: E+ p& z3 r% {6 B( ?    printf("The last one is NO:%d\n",*p);
, b% L5 T, A- G/ U     getch();, V5 H* Q7 d4 p  g6 o3 K: X

- X3 D/ L4 R8 n}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;3 J+ }$ _  N, D
namespace 又费马达又费电$ y, {! ?4 `1 u- l  q. g4 S
{
- v- }- \6 V1 o! P, K% I9 F    class Program
8 [, S! E7 }% o: b. Q: r    {. t8 D+ n. B6 ~* I
        static void Main(string[] args)
5 O$ _$ E9 k# u        {
( _7 O$ V/ }3 e! a            int m, n;$ F4 u$ \' ]% ?% D0 J
            Console.WriteLine("请输入数组长度");
6 h+ J8 ], r. p$ c2 m            m = int.Parse(Console.ReadLine());//m为数组的大小
, P6 y( \* j( l; a7 _/ |! N            Console.WriteLine("请输入要截取数字的大小");
' w, z1 W! j' O5 q* Q" v% s            n = int.Parse(Console.ReadLine());
, @; A2 o, R6 f& b+ _$ ~            int [] numw=new int
) n8 E' n! F0 g8 I) t# ~
2 U) Y; D6 m0 r4 A# H1 ^&shy;&shy;&shy;;
  q: W* s% d. O! K& x            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数, a6 r6 w1 f' K$ O. S, F3 H
            {
4 v( U* ^( X: y' p$ v0 [& u! k! K                numw[j - 1] = j;
% w  Y) _0 r6 J6 p( E4 f+ Y1 n            }
: j2 \$ F2 k0 W7 A6 s$ V& `) `            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!9 V0 {: j1 b6 t2 a# x) D3 h
            while (d != m - 1)
. D- s' L/ W9 d2 F2 w            {, ~5 @. K" x# Z( j' d5 T$ U! @
                if (i == m && d != m - 1)
6 U5 `3 y4 Y  \/ G- L( L                {
2 O9 `- s( f$ _7 B/ o                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!! Q1 h7 _8 y5 h5 f) s1 h
                    continue;9 G( x5 K5 b2 }; l& x
                }
8 i3 M) u! x0 s                else$ v% H! @+ S& p% u5 u4 a6 G
                {
5 t, l4 ^$ F* s                    if (numw[i] != 0)
6 V  q  j$ k7 J4 g) [( Q                    {
; M) k/ k+ {% y2 k; L" u- E8 i                        i++;
: Q) f2 d! @# e8 S$ h2 E7 f9 d% y                        k++;
/ x/ L( N$ g6 a/ U. Y                        if (k == n)
8 m5 T3 a* R$ ?4 j. b                        {6 T3 |8 z: O1 q! o! n
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
' j# s( u% }9 P9 M) E                            k = 0;. G3 W+ O( X3 _7 j; U. w# o$ \
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1$ w' ~  }8 G+ Y$ W0 [! b
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 f% z+ O8 T# h0 g                        }
7 d" s( J7 r& }3 H: b0 @: |                        else//输出暂时还没有改变数组元素的值
8 g& ]4 p* b3 l) s9 e9 d7 ^                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: d7 w0 E) t# e/ \# W% ]
                    }
) o/ T* p$ k- E; L                    else
/ V. a, G8 [' ^                        i++;//数组元素为0,直接跳过,不计数。。。
( w% A2 {' f' O3 M: l  ~' f1 Z                }
" U4 P6 D; _+ J( x
6 {  V8 P# l5 t
( q$ V$ @, ?: a7 T$ l1 A            }//结束while循环
# c8 s, l7 h1 \5 }6 a            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦+ r* r, W; j. C1 s
           
5 w, n8 w  E3 u, k; K                if (numw[i] != 0)2 K" B' _0 ^: P# r/ F4 B
                    Console.WriteLine(numw[i]);) S1 X* ?% m& M1 a* R
           
; ]; a( `7 B( G6 M& M% ^            Console.ReadLine();
: S/ X' {/ I9 J4 M+ ]5 u6 B- w        }
0 s# c& K7 l/ D6 t1 r. _* U    }% T+ ^! Z, G( }/ w6 E
}- B7 `: V: a  P: _# G* j
小甲鱼最新课程 -> 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-4-5 05:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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