鱼C论坛

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

猴子问题

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

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

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

x
大家好!; W1 I. b; Q# m- d8 q! S
这几天我在忙着编一个问题,我用了一种方法编出来!
5 {6 |) j# Z+ C0 B% ?" b但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!: h4 D6 l3 V, R$ F
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ Q) J" F% F6 r* s$ _! L: E* `2 h& b! X/ V! l# n

) F1 R1 @. r) y) J
                            题目) l- d) ~) d& ]7 R: Z* b6 i
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
% @, T) z- u5 l5 l第一种方法:利用循环链表
2 [6 q. u3 o9 _! T2 U#include<stdio.h>; l, W7 j/ O  M4 D; O  k8 q- U
#include<malloc.h>
8 ]/ y9 E4 n/ Z+ g& d" c#define M 8            //共有8只猴子! L' o$ ?$ ^! x; w0 I) c$ J- k) t
#define N 3            //数到3只时退出第三只
" C' ]0 {/ H" e3 \4 ~typedef struct monkey0 H0 ^7 T& f6 l$ x
{int number;& Q  W: w8 f  }" {, M
int flag;0 j& ?3 Z( l8 Z1 W; b5 a4 t
struct monkey* next;/ [, s5 [# j7 `5 `( F. Z
}MONKEY;+ A  g1 p& H3 R3 u
main(). w, `' y; E  k+ P
{ MONKEY *head=NULL,*p,*s;* \3 P! g# _( J. ]# ?2 f' E
  int i,sum=0,count=0;4 j$ [+ ]& A' g( \& w
  clrscr();              //清屏
" H, b- m6 M% ?5 n7 m  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存8 @4 K: }3 r8 N
  p->number=1;p->flag=1;: l& @- u/ \# }" s. }
  p->next=head;
% Q* T( U; {2 e4 E, q) T! ^  head=p;
* i4 l, Q# V$ k& w9 K/ y. ^3 u& g  for(i=2;i<=M;i++)% b* Z) t: u+ N
    { s=(MONKEY *)malloc(sizeof(MONKEY));
3 Z- B% s* d6 h) n8 @8 l     s->number=i;s->flag=1;
. o, {1 G) _, k5 R2 N1 E     s->next=head;% g* @9 `" P! d
     p->next=s;p=p->next;! d% H' N) z4 Q7 V0 f0 N
    }
, K" s6 N0 f) ~$ j5 V    p=head;
; X( X" t% L  C' U# L   for(;;): L1 F. {- Z, d
    {if(p->flag==1)
9 I. h" Q  S& r       count++;
& P, b' g" J2 @% k) g, a* o/ T     if(count==N)
: U. q2 T6 B* @9 A/ K        {p->flag=0;  i- ]( F. ^: O. a
         count=0;" C4 F" g! Z* X  _+ U( f3 U5 i9 o7 X5 ]
         sum++;}
. L" s5 Z$ a1 H2 A; F! H7 N     if(sum==M-1)8 H0 ?. g# @8 _
        break;
: V( G' S- _: n$ l     p=p->next;
6 U2 R) I: P* J3 A3 @    }! W2 f1 D2 ?; f1 j- n3 P8 o
    p=
5 P% H- a1 {+ n5 I; t0 M$ n. Q    head;
: {/ y% {, d! W! f) e    for(i=1;i<=M;i++)# ~1 ]9 L  A! |! \2 @( a6 @3 Q
    { if(p->flag==1)  Z- j% c0 I6 y$ n/ m' a/ d
        printf("\t%d",p->number);
1 G( n8 F5 b8 J8 Q      p=p->next;
/ W* i& z3 }1 g, h0 p- i0 W    }
% J+ [4 y  m3 _3 w
, f+ `, U. g+ [: h+ Z& _
& S  e; s4 |% r7 u: `# O/ r7 h, w
3 W& A0 d# c/ I0 K$ `# \7 d! m1 A}
7 c' V1 ~8 v. l  z/ U/ w. B0 N
第二种方法:数组" H6 b- {% N3 K4 a' q
#include<stdio.h>8 `1 n+ V, S6 ~
#define M 8
+ h, K* N2 E# e- l% ^struct monkey- m8 U- `$ w- f/ p& {6 v1 E9 a
{int number;% Z7 A( e6 t& H4 I1 Y
int nextp;& |/ x( F1 R/ K3 L0 |6 W
}link[M+1];
4 q# P9 a: {9 c6 ?# {7 I
9 R$ N" i/ s0 t# j- n5 d0 \" O9 v- Yvoid main()3 i8 R0 T4 z2 N: l4 k$ ~) l
{int i,count,h;3 M6 }- J5 }$ \7 G. o
for(i=1;i<=M;i++)
$ q4 _+ E4 l7 A! K0 B4 v{  if(i==M)
2 O- [) p6 w7 {+ e4 d$ H& }   link[i].nextp=1;
+ z/ r' v" D( _- @9 N5 j   else) k5 C. e/ O) X) D' o/ T" u
   link[i].nextp=i+1;2 C4 _$ h1 y! t
  link[i].number=i;
9 w, U7 m1 }% |) Q; R}
$ q$ H1 M/ A7 e$ `1 @/ Kprintf("\n");8 d+ R0 D/ N( B
count=0;
5 l3 O0 P- |/ u/ l2 w% ih=M;7 F$ ~" _( s, _* N
printf("依次退出的猴子: \n");5 r, K. ?+ u% @; z5 |) F4 k4 x
while(count<M-1)4 E5 n. j/ g: P' A" x+ a+ }
{i=0;- v3 u7 N+ @7 p4 d. V0 [' L
while(i!=3)
% j# @- }# c/ k6 A) R9 {{ h=link[h].nextp;9 n: t: K, g7 d/ }! [
   if(link[h].number)
: V% Y, Z  w" {* P     i++;}
8 B' ]1 K/ _. z! s
3 C  [( K. ^4 }2 H% \printf("%4d",link[h].number);5 X% ^5 e9 t0 l% e; J
link[h].number=0;+ o6 O7 M; @* e( I- y
count++;  B7 ^- p* v. E$ }
}
! q/ B2 e9 h* v1 l% E( `: y" s2 l2 @: n5 v8 _6 O1 w. T' K
printf("\n大王是:");# ~: g) r8 w5 L
  for(i=1;i<=M;i++)
; o" [6 r7 S6 m  A" {  if(link[i].number)3 a9 b  B5 ]2 b/ y
    printf("%3d\n",link[i].number);: B  M4 e( J- U4 H) |

) f- n9 p7 S2 H$ j% O, \6 s! D& y) p9 D6 ?) q1 V' m! g
}

$ S- ~6 O# _6 O  e$ G第三种是普通方法for循环

, t3 i" l& T# M, L#include<stdio.h>
0 a& z/ S9 m: V$ L+ Mvoid main()9 l  K) p1 V/ ^6 E3 X+ l: t
{ int i,k,m,n,num[50],q,*p;
3 B% Q$ p% M- A    clrscr();
3 I9 B# ~2 g  P8 j5 F3 b! P0 i' h& l   printf("input number of person: n=");+ p: |0 S2 g, h
    scanf("%d",&n);
! r2 k# S: ~7 ]* gprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
9 }' B2 D; x" G    scanf("%d",&q);
0 z. M( `/ Z  t( T0 n8 H   p=num;
( _+ Y  {$ P+ I2 ]9 z( S  for(i=0;i<n;i++)9 `: i' [* y: a& }# c( ~
    *(p+i)=i+1;
9 o8 ?, x0 V2 V7 J+ o$ d) ~! X4 @   i=0;* L  x( s+ u; ^
   k=0;$ r; V6 o' S8 b( r2 _; z  ?4 Y
   m=0;% u# A9 p. h/ b2 f8 J# A
  while(m<n-1)
: W% T7 n* b' C! ~5 B: q   {if(*(p+i)!=0) k++;
# ?, O, B  d; B& q. K8 V# q8 r7 R     if(k==q)0 i0 G" K0 @7 i& @1 B* _! [1 u
      { *(p+i)=0;/ l9 i- X2 M7 \2 W) d
        k=0;* x# u) D2 J  D8 l6 j" f
        m++;* w# n5 t+ J. Z/ }; G$ w
      }
. b, B* ^0 B3 Z: K9 i3 d    i++;- `$ v: ~' i" v, o) k
    if(i==n)i=0;* ~9 S* w6 f2 t9 O6 C- n
   }
4 Z" C7 f2 a% m  while(*p==0)p++;) p5 c" `. _3 _( A& _
    printf("The last one is NO:%d\n",*p);
/ o+ K7 ?7 s$ j9 i     getch();6 Z$ E& H( J* \  j
4 i1 {/ z" p; i1 t/ ]$ H. H
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
, [# p0 V5 k( D' y8 fnamespace 又费马达又费电
* Q& i3 D! ?. i8 m& Q. B6 O( ]{& Q2 m! B; A% O! O, I
    class Program6 N$ Z/ o5 U- D# t2 Q0 ]4 a8 A& V
    {
3 Q& V  Z/ ?4 t        static void Main(string[] args)0 v: Z" \% s: W$ U
        {
% @. ]# m! D& J8 p            int m, n;
! v! Y6 u1 a3 W8 V1 |- i. |) v            Console.WriteLine("请输入数组长度");/ Q/ s( w8 z* d0 ]8 L# \
            m = int.Parse(Console.ReadLine());//m为数组的大小
! m& X& b) E  m' A3 t# \3 C            Console.WriteLine("请输入要截取数字的大小");6 q) L3 w% d% E5 |1 ^
            n = int.Parse(Console.ReadLine());) W, \3 M: |7 f7 |
            int [] numw=new int
& Q" ~4 q4 F/ v! l3 S0 H0 L% n- t% M6 F6 V# q
&shy;&shy;&shy;;% W- ]: P0 H2 n' T/ Q' w, }
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数) q- f' f5 X! V( |
            {
7 o+ Y+ f& e' T) k- }! l                numw[j - 1] = j;2 f  [0 k# c6 E0 Q
            }
# Y. |" q# ?" R  Y3 [+ P            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
' M1 n4 S6 J) d( I6 ?            while (d != m - 1)& W  k$ G6 K3 M9 W% v
            {
: Y; P1 K$ c0 D( Y) y3 i4 k                if (i == m && d != m - 1)  U( p0 ~2 `) L" w/ @; T1 P
                {
' K+ p* v4 B1 T$ Z+ q" c                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
& c! \/ t) P5 G1 F) H% K                    continue;
. O: j+ o  q+ y2 ^$ A- J                }
7 S! h0 A- I2 i6 n3 x                else
+ Z/ G& }! r0 V                {
- k. G6 h; n* }! J                    if (numw[i] != 0)
4 W* B" w5 M5 R" E                    {7 ^  @4 Y! q" L5 B6 D
                        i++;
1 d) X8 C, b$ A2 `& g+ M6 }                        k++;9 Y9 @1 [) W3 }
                        if (k == n)
. Q( |3 ?# j. C" q. u* C                        {
) W9 R3 F3 H7 l, ^) T7 X                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
$ v2 t+ ^3 o4 i% U9 r( y                            k = 0;* G5 E2 K- f, n' O6 t8 {' |3 x
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  [7 b; J2 O+ F# \
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 v0 k1 {. k. ~6 N2 @                        }2 k" w9 Y) ^( k' h; Q7 Q
                        else//输出暂时还没有改变数组元素的值
4 N1 A" ~6 O# {, P7 d0 b3 y                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 w7 D6 t7 {" E. e  u4 _
                    }4 y4 l( G. T/ i2 G; c
                    else- {: W7 B, t( h9 U- N' Q/ C
                        i++;//数组元素为0,直接跳过,不计数。。。
, B' ^4 ?% J! y* j) {9 \3 k& N- R                }4 `4 r' j# f3 v1 B1 ^, R( g

9 Y: i; ^4 q2 p4 L# b4 R) x+ w$ c$ ~9 U% |+ i" C& f# x
            }//结束while循环
; _  _+ f! n8 |% h& W9 E            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 u1 e: q& C: [) \) h7 t
           0 _  v' }1 b9 |. d  n3 P" Q" n7 v
                if (numw[i] != 0)4 [# p/ }0 N; \" w& o
                    Console.WriteLine(numw[i]);. f# h: c5 ?0 {; n7 h2 [8 ?% F
           
+ R0 E, u( N& o7 E* q            Console.ReadLine();/ P8 s# [& v  I( {3 @( L
        }$ g/ v: e# D* O! B1 }5 _, D7 w
    }+ L0 q4 ~" u% `3 K# B4 X3 c$ b! D( w% V0 q
}6 }" Y; [# t5 o4 m$ L" x6 ?
小甲鱼最新课程 -> 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-7-8 02:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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