鱼C论坛

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

猴子问题

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

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

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

x
大家好!& j7 v3 |6 d& ^8 W# i: C0 x
这几天我在忙着编一个问题,我用了一种方法编出来!
2 B$ l5 k" Q7 G* k/ [但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
/ b( j0 O3 Q2 H7 {  M注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ; k, v: o/ ^) P. j# r1 K( u5 `
0 U+ i- _! c# e3 W' ~( M
! \  ]9 V; S: n0 I
                            题目" I% q& h* L. s2 R. [
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。; O4 {% D# W7 ?$ R0 V! N$ Q2 \
第一种方法:利用循环链表
9 f% J# @& D7 l) `. z! I#include<stdio.h>
0 D0 M" H, e/ c#include<malloc.h>7 i5 l- d# G8 i6 I- c
#define M 8            //共有8只猴子
" E* W/ v7 U  H  m2 z: f5 R. x#define N 3            //数到3只时退出第三只
" d  r6 J' z5 ^$ ^* @typedef struct monkey
- `- |$ S, s& d/ ^. a/ ^$ M{int number;2 H7 l0 N" x2 `6 [9 H" G5 m
int flag;2 f, m5 h6 A; @3 a& [
struct monkey* next;1 r% u5 @6 d+ ?9 ^# N) w- \! A4 q
}MONKEY;
1 a4 a  o; X5 n2 j3 \8 vmain()
' f  G) `* X' j/ ?! n! }" l! N6 Y{ MONKEY *head=NULL,*p,*s;
* o/ m* t- _9 V* N( Z+ B  int i,sum=0,count=0;' H2 B  ~5 t6 o8 a8 A1 j' _- q; o4 T
  clrscr();              //清屏3 W' I, J- W' X! W! C: _
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存' j- m. E5 c  ~9 ~6 b
  p->number=1;p->flag=1;
6 i) o" y4 v8 f& z8 G; {. P( g' e, P  p->next=head;$ A2 z5 i, C9 P$ R! X* J
  head=p;; O' p) s7 n% b3 c+ Z' X- W
  for(i=2;i<=M;i++)' {. n' g8 _% u0 M0 I7 x5 d/ d
    { s=(MONKEY *)malloc(sizeof(MONKEY));/ i8 }" S' Z! k# @1 e
     s->number=i;s->flag=1;
, i- S* A% k; [6 K     s->next=head;
- Y, ?7 ^" d% f( Y, i     p->next=s;p=p->next;
1 r3 U' c. W% ^! w9 i" ~    }) A" d6 b8 Z2 V7 D( N7 _. O1 O
    p=head;
4 V- S! T" S. b# ^1 W, y$ @# ~   for(;;)8 E: ?( q$ [% l# p
    {if(p->flag==1)) l  h: B4 f* H2 g: I
       count++;
5 G; Z0 i1 l  [     if(count==N)
7 X- \6 n7 O  T/ u8 b        {p->flag=0;. q+ _" D' S6 v9 u; E
         count=0;
: p( n5 M* X4 K% g# w         sum++;}
3 E4 B, \: T5 v: i- B     if(sum==M-1)  X7 V% P8 R- d8 J" G1 x6 a
        break;; O9 k/ K* Z, M+ c4 E+ w
     p=p->next;
4 D0 ]0 g) ]# F4 v4 ^: L    }# _6 n6 E# A- V5 [* [# {1 j
    p=) [: G5 i1 X0 a' |
    head;
$ m# `1 U5 X4 f7 q, l6 E    for(i=1;i<=M;i++)
. t# D2 w+ h5 T& Q; ~+ v    { if(p->flag==1)
# B* k4 T2 ]( T. L8 N. x. Q        printf("\t%d",p->number);( L2 a  |$ K! R
      p=p->next;9 \& ~3 t6 i" `  a+ X7 W
    }# y# P4 Q/ A' o2 |& \* c

. b. ?$ |. a, |) @% D; K% s: q+ v

: R( I" y8 A, T/ d}
; j! x8 F8 Q3 \! t8 A( G* k
第二种方法:数组
6 R, J, H. P' E  w% x3 ]#include<stdio.h>2 i$ ?' g; H1 _, T6 v
#define M 8
- C+ B0 c( N0 w7 pstruct monkey3 V4 u: }2 R# c$ P& }' Y
{int number;' P) p* G) l: v
int nextp;8 A7 [0 Y5 p  F2 ^
}link[M+1];
4 A# \+ m6 g& _7 Y( r4 H. M/ D
) i( A2 ^1 c" n' @( Y- q2 qvoid main()
2 {8 k. i( o3 w{int i,count,h;" n) F) r3 b& A. ?
for(i=1;i<=M;i++)# q% |2 x) j% l, k( q; h
{  if(i==M)- I+ I- A0 _: N: |" V: t8 `
   link[i].nextp=1;+ d, D0 @- C  L4 ~
   else
1 N: b. a: ?: N# |$ O9 X7 D   link[i].nextp=i+1;' U4 ?5 A, ~! u4 \
  link[i].number=i;
5 ]6 U: y; D. w1 r* Y6 H; k}/ n% G  }, ~+ p3 x; B; F0 }
printf("\n");
/ }- g' u$ \6 Lcount=0;7 |5 y. Q8 i% c$ T* z- ~1 [$ A; @
h=M;
, [( v6 [' R, v# M* c  wprintf("依次退出的猴子: \n");7 e( |# t9 u+ `% A3 c1 b9 _- V$ R* t
while(count<M-1)2 Z3 v, ]0 \) }; o
{i=0;
+ S) `1 |. \6 T( G8 Wwhile(i!=3)9 Y3 t* h& ?$ w
{ h=link[h].nextp;
4 `; _3 }* b8 V4 e+ |; |   if(link[h].number)
$ a7 R" {: y6 D     i++;}
( W1 Q+ n' ^4 F8 L9 }3 O/ X, u8 r( V) h: `! Z4 i
printf("%4d",link[h].number);9 [' |" i* B( P. d8 H% N/ q
link[h].number=0;4 A5 x% J# f, B7 D/ Z! {5 t
count++;
4 I' F6 _; `9 B: E: W# w}
) a3 t) b% M; S. T* f3 F: e. W7 ]* [. J7 Y
printf("\n大王是:");
2 f3 g! f* p) O; M3 j% f9 x  for(i=1;i<=M;i++)+ `0 c0 f# r7 t5 g3 _. S3 C& E
  if(link[i].number)
. I( p# w' m: b# x. D9 a8 G    printf("%3d\n",link[i].number);& b5 }' t* I4 b$ e, a% q
8 T, P+ h" H, k) a& A/ g7 P" h
  S; g9 u1 r0 E' D9 G6 N
}

& m7 E) W: I1 |( j5 X% ^3 s2 g4 c- n第三种是普通方法for循环
* a- V9 @9 {6 B9 a- I7 D
#include<stdio.h>/ |/ a1 i" {/ k6 T* A0 Y! M. J; c
void main()$ C$ A; b& n0 k( a! j- X
{ int i,k,m,n,num[50],q,*p;
% I. P" k3 V) D4 n    clrscr();
2 e; r) `7 x9 G$ {   printf("input number of person: n=");* B+ G& H! L  A7 c( Q
    scanf("%d",&n);
1 x' f- }0 N0 _4 M! ~" Wprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只6 C( k, W: W$ w# x  F: i1 Y
    scanf("%d",&q);
2 m3 [1 X5 T' P5 P" Y& V) l) Q! Q9 E   p=num;2 e* |' k2 ^! d- H1 T
  for(i=0;i<n;i++)0 G% P! i2 ]" p2 u1 N
    *(p+i)=i+1;
3 Z3 b6 `  C1 n4 @   i=0;
( r+ A: T+ f+ O3 h- K: L7 ?   k=0;) N) t; a+ T: v0 M+ b% T
   m=0;
7 d- G5 r% S6 Z* o4 p* j; ~. P; c  while(m<n-1)
+ \% k1 }# ~+ o- ~   {if(*(p+i)!=0) k++;* V1 G. j( ^3 I% J  u! P& {  `
     if(k==q)
0 q- i5 ?  C, `% P$ l8 L      { *(p+i)=0;
% d& a9 s5 M, v: I, q        k=0;: W' A/ M2 ^- C: T/ K6 Y
        m++;
! Z% Q6 o, O$ q      }( ~$ A7 f1 l2 U5 U/ f
    i++;: J% B9 [+ ]$ ?
    if(i==n)i=0;
4 h) H8 U( y) n* b+ N$ ]/ B   }
) A1 X' F' Y% C2 M& P  while(*p==0)p++;
, t) t- e, t8 o, ~# p    printf("The last one is NO:%d\n",*p);$ C4 [5 s6 _9 l( v# U
     getch();
( p+ a+ e5 _- t/ F$ g% F, R( B( d; `9 F4 B& I* F! t
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;) g' E( o" S  D! t6 D0 ~
namespace 又费马达又费电; |/ x6 b& e# O8 j$ P" k
{3 B, I( K7 }7 \1 `7 `
    class Program8 s/ n3 M9 e2 ?! Y8 g4 T
    {
/ M  w7 D* A  Z& K% }( T7 F        static void Main(string[] args)7 E% X  A+ G' s4 u
        {; g# G  _+ e4 N  U/ k" S
            int m, n;
% Y0 R5 h# T) B            Console.WriteLine("请输入数组长度");# F2 A; @4 o" L. K. B4 k
            m = int.Parse(Console.ReadLine());//m为数组的大小
6 u( f. g2 J1 K. x            Console.WriteLine("请输入要截取数字的大小");
+ {/ x# D  v$ M+ D: w: X            n = int.Parse(Console.ReadLine());, v' ]( |3 [' H: N8 f. N
            int [] numw=new int
( w! G% C6 H& @# W
4 f8 P% o" M! R4 f5 g- O( J&shy;&shy;&shy;;
; ^1 c/ A6 d( v1 Q: |! Q            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
  q7 W* T4 c, q0 ]; ?  G            {* w( Y$ ~! w4 t2 Z% _4 D
                numw[j - 1] = j;
' K6 M& z. E. C* f5 m( }( j            }, d0 r) a- e' ^4 R
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!% W4 i/ x& [; X" W( q+ w
            while (d != m - 1)
8 \  u' G( G- a. O            {
- S( @# l. N4 M9 A) @                if (i == m && d != m - 1)
) W$ J+ c4 Q5 w6 f) F& f                {
6 i! A2 z. d9 Q& N                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
* N3 }9 w& h; u$ v# ^' `4 w                    continue;
6 e9 c" k4 f+ m, @0 A& L/ s                }
9 }" ~- U9 d/ g( f7 r  O: {8 C                else
. F! X+ S( ^( ~+ O/ {                {* y4 F( W/ K6 e$ b4 D& \6 \" S8 W
                    if (numw[i] != 0)
6 g5 w1 F* L# y  Z& u. V$ n8 O                    {
. T, @; F1 X5 e. j- ^                        i++;
* H1 u0 H7 Y  N; `! g                        k++;+ Q6 m( B- h9 k1 u; J+ V+ p& T
                        if (k == n)# C: F0 g1 t/ G  ]6 Y5 ?$ S8 r* A
                        {
, F+ D; j7 A- u) ^                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
& H3 i2 A' |& e/ w                            k = 0;. e2 {5 [7 k6 A* C  k8 }
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# y% N; E# K* B$ W7 ~: ~$ c  e                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  S, A2 [! k: }( x3 J. X
                        }
0 e* }2 f) a8 l3 Q1 y                        else//输出暂时还没有改变数组元素的值
/ X# F0 s$ ?0 Y; ~3 d                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( N# v/ z( a; A; R' |) R
                    }- l0 {* E* N# @$ R. m
                    else1 O7 H# g: Q- ^, }8 w
                        i++;//数组元素为0,直接跳过,不计数。。。5 z6 [7 w- n% k7 {4 E7 L
                }% F2 \1 p9 E9 S. y  j) T6 `
4 _2 ]. `# d. q5 _+ a/ k) U- ~& X

7 y& b+ n4 k& B! ^( M9 {            }//结束while循环
) D- i7 k1 J( H) P) n0 S            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦9 p: V; k& j- y( v. R
           7 U0 W  x- d  d- d3 m
                if (numw[i] != 0)# J' d7 g( u* i. B2 Y) ?' c
                    Console.WriteLine(numw[i]);
" N3 N- K5 W! l           
& ^( F; Q* ?7 U/ e- N4 G$ T& O- V            Console.ReadLine();) i$ q& t  w1 T+ V
        }( n7 I& ~% P& p
    }1 J2 J* L1 i* ~$ [8 p% b
}$ Y, u# j0 s# V5 O) m: r
小甲鱼最新课程 -> 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-31 18:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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