鱼C论坛

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

猴子问题

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

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

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

x
大家好!7 W( a3 `* W9 k& s) T
这几天我在忙着编一个问题,我用了一种方法编出来!: S0 \3 s2 w7 R- \* m
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!2 k/ G, C5 s1 Q2 C& Q( `$ `
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 - q  s. o$ i; P0 i- Z; a; }8 |+ P
, j& x% V) k3 n; [2 P* M2 \- i# ^# H
( J" h7 ]) v* T" L% e' H$ ^
                            题目/ n: p3 x( F& N( x1 L+ E! H* M
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。$ _1 P0 v" N$ P; M
第一种方法:利用循环链表
* b# G  L& X. q8 v2 K0 ]" |#include<stdio.h>) y; {* D; D  f% }
#include<malloc.h>
$ }* p! w$ L! f& B5 Y% H#define M 8            //共有8只猴子
, n/ n1 Z4 Y7 y/ w. M+ f#define N 3            //数到3只时退出第三只( |* B5 L8 I% V' X
typedef struct monkey% Y# E. W. l7 U* l# ]% d
{int number;
1 u+ B+ |) |% S1 U- D6 iint flag;- ]3 z9 R" e/ P3 s$ T3 r
struct monkey* next;
3 O9 M, q! Z, K  X0 W- U# M4 y, C}MONKEY;1 U9 x3 S" x! Q- x) J
main()- o  v8 t1 ^# D1 H3 X9 @: |0 ~( P
{ MONKEY *head=NULL,*p,*s;, p7 o0 Z/ I! n
  int i,sum=0,count=0;% H" t6 Y% R- k; l0 |' Z
  clrscr();              //清屏1 F4 C& h9 @$ `/ ~  o
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存' u5 p  e% g0 v) N* f
  p->number=1;p->flag=1;3 D$ [, q% }: x! d
  p->next=head;
  [+ z+ C/ b7 X6 n9 l& F! \. E  head=p;# d, r, I( r6 D( q6 D
  for(i=2;i<=M;i++)
' C/ ^( J" m( @: z! ?) J; Y( m# B    { s=(MONKEY *)malloc(sizeof(MONKEY));* G: D/ V6 u4 o/ O
     s->number=i;s->flag=1;. J# n# b; C+ s
     s->next=head;
. R) C* P9 d! o3 e% s7 _     p->next=s;p=p->next;. F; L" V6 r9 o
    }2 Y6 j2 q* B/ j1 j
    p=head;) A* G- |6 h" V1 L
   for(;;)
* i# x, G% D* k# B0 B( C4 Z    {if(p->flag==1)/ e/ o+ k# @' ^; e3 y* N
       count++;& @6 `  j: S, [. B$ j
     if(count==N)
; D  s1 @1 q+ y5 k3 m        {p->flag=0;% S  v4 u& Y; O% A" T  [
         count=0;' B; O5 Z% O2 g1 ]
         sum++;}
. n, V  ?0 C, w5 |8 d4 b     if(sum==M-1). X- o; K. Y  ]8 I0 G8 W6 j) Y
        break;
1 K& w' o, _4 g+ k- M/ |. f+ C  |     p=p->next;- G4 G0 Z3 R4 `% l% |
    }
2 O7 I, w0 C) I# A, ^% j, {" C    p=8 L+ ^8 G9 G* i0 j& N9 A, F
    head;5 `% h/ {$ ?. |0 c  Q/ M" g
    for(i=1;i<=M;i++)
. {' b- u7 j; D0 o    { if(p->flag==1)
; U. }  k9 {6 g- P0 o: ]: X' w) J        printf("\t%d",p->number);
0 o5 u6 X/ \. ?      p=p->next;  R3 g) v1 @2 X. ~
    }
% D4 k& B+ ^( I
- u, z) s0 I$ r, U) L* m
* {  u" Y5 ^/ Q4 W0 v# [
6 f% I6 [- v; i" _) j+ h1 M" K. R( Z}
' g! X1 t0 j; w2 _; _
第二种方法:数组
6 m: W9 \* m0 ?' u2 |#include<stdio.h>
2 x  l; B" b. b, [( g6 i#define M 8
" [! H; n4 d/ e( X- `struct monkey" j4 n* b* a! `0 V  V# R$ s. x
{int number;' X2 L; o: Q$ e7 y* w
int nextp;- w2 n! [8 Y) V# `& F
}link[M+1];
, V2 W' c1 U7 p( l; Y
3 ~  m$ q7 x! M" Tvoid main()
3 S: {; H6 b' B% R& V3 p{int i,count,h;1 n1 [# g6 A% M8 k8 @
for(i=1;i<=M;i++)
! p, e& G1 \2 h0 x/ x% j{  if(i==M)
6 ?0 M! i6 m5 K. z+ d8 Q1 V4 g   link[i].nextp=1;
1 c2 S" \: q& ~5 I0 e   else+ C$ }6 l- H# n$ d7 }
   link[i].nextp=i+1;. e/ z* P% k+ j# t) b
  link[i].number=i;
+ t/ c1 L2 u$ R  B: C2 c' T7 r}
7 O/ y% u2 z) A# mprintf("\n");
- ^& P) _3 W- {, |# kcount=0;
: X' z" _# c" n, r* P8 @h=M;
% G; g0 ?$ |5 m( Qprintf("依次退出的猴子: \n");
4 @* c, ]! G" s0 s# Uwhile(count<M-1)
7 }4 c1 _3 i) x( ~/ Y& r{i=0;; S: K- F/ s  u# f& N9 ]
while(i!=3)
/ n. H) ^9 p4 h{ h=link[h].nextp;5 x0 t' y1 V1 ]: s
   if(link[h].number)
- A5 K) k  q* r- |( @$ v/ g( P     i++;}
: V4 ^  s0 ?' W8 K+ v
* V; \, ~9 x: j# @& ~printf("%4d",link[h].number);- H( k) ^" _, v7 j% }
link[h].number=0;
& I3 E6 a6 p! H4 i& Kcount++;
8 I+ @$ `& N  V% `6 q}
" m5 |& G0 H5 B# u% j# h% b# J0 k% `+ e9 Q( {: N
printf("\n大王是:");8 u& X/ A$ c2 b
  for(i=1;i<=M;i++)' I* N9 l8 `! @7 ^0 R) G# C
  if(link[i].number)' L- f' T, y/ R1 m" q7 v
    printf("%3d\n",link[i].number);
0 V1 Q0 n) J& I8 W' u0 B
1 T# L; p, x# Y3 Z6 P/ w- ]  b% z# n
}

4 L" r# x! {4 R5 D2 J5 \第三种是普通方法for循环
1 T- h9 a2 ?, B+ @5 V2 Y1 @
#include<stdio.h>
1 b. M) s/ T! i+ Wvoid main()' |6 t3 j9 r/ H
{ int i,k,m,n,num[50],q,*p;; U5 j7 m% |; s. K5 s: O) I2 W
    clrscr();
" Y6 d; b" O2 t( u   printf("input number of person: n=");9 t- c. B) _# E. ~% N( G
    scanf("%d",&n);- \  U+ r5 r3 p$ B
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
. w" `$ q0 F8 P& @! T0 R    scanf("%d",&q);( s+ y, ?2 _4 L# x+ K/ o6 I+ r! i
   p=num;$ ?& {  E0 @. y, ]! s
  for(i=0;i<n;i++)+ e- [) S1 e( X6 v
    *(p+i)=i+1;
4 `( S4 O7 p; J6 L1 V   i=0;  p  U: }  A& j
   k=0;. i9 _' A% u0 V4 x- M9 c
   m=0;- n: T5 ^6 I2 C7 W
  while(m<n-1)
9 l" @( x% u, ~  K, Y; R7 X   {if(*(p+i)!=0) k++;7 I1 y' P& W# [8 e- H/ A2 ~
     if(k==q)
4 C+ W, j; s) t      { *(p+i)=0;6 t' B& r# n- `, [! z
        k=0;
1 D* u9 d( N; T* X% t: d% ~3 A        m++;5 m) \* q& e# n7 P& \7 q& k" @
      }
9 J# a: t2 N4 ~8 V1 `    i++;- g) ^9 y' p; ~* s0 A5 ~9 B
    if(i==n)i=0;* R4 p8 p; a% e1 b/ x: [
   }8 e0 Q: B* H- O3 e8 ]
  while(*p==0)p++;
" R' l0 Y8 g7 r: b  ^. W    printf("The last one is NO:%d\n",*p);
# D% A0 L1 N, l% j$ z     getch();  ?* ^+ i9 Z" d" l# |. F' s; R

( `; J# [/ a5 f% r, M* b, R}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;1 M  v* g* F& ?) A' j8 b* Z$ C6 n
namespace 又费马达又费电
& \2 T+ f2 A2 o{5 u( j# R$ T# t  B
    class Program
& N. t% U, X" T) T    {
! j+ A# u/ P; D5 u" J        static void Main(string[] args). ]" K! B( e( H0 T& B2 f$ }
        {7 ]: v3 Q% o/ [0 U9 l
            int m, n;
* K3 v; Z1 c& v  U1 i- F" l            Console.WriteLine("请输入数组长度");
* t: {5 w' v4 H3 h( h' {; V: J            m = int.Parse(Console.ReadLine());//m为数组的大小! H1 n$ f5 g6 U8 {( g. }/ l
            Console.WriteLine("请输入要截取数字的大小");
9 F; P4 Y+ a4 f            n = int.Parse(Console.ReadLine());
, s0 \0 x+ ^' D6 c9 h            int [] numw=new int
" o& \& ]; N% O/ @, E/ v5 \7 z
2 l6 v" o/ r: ?&shy;&shy;&shy;;3 [6 i" C( ]. l! r2 F1 F' I+ X
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数' V$ r" `! L: i2 y) R
            {
# w) W7 y* N. |, A7 i. d& [; I4 I                numw[j - 1] = j;( _" W& A7 ?( S. |( S' |
            }: ]- |" v6 A4 D+ q/ z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
8 a, g) g' ~, g- t7 ~            while (d != m - 1)
! T3 r* F4 x) r            {  I+ Y- ]9 v9 Y0 j
                if (i == m && d != m - 1)& b1 X. w  t# W5 f$ @1 N' ]
                {& X  m, Q5 o4 {, s/ d! [
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
+ O7 _; C6 r, a( R% Z9 {" `! a                    continue;  d7 X8 p8 I% v4 P; j
                }
  c! K7 A9 O$ f. N( X/ c                else+ A2 ~8 }. W/ ?; |7 \  R
                {
- {# K- g3 V. Y' t" U6 I2 X                    if (numw[i] != 0)
0 i' L5 a% k! A6 Z7 E3 j; q                    {
( H3 m8 G  v) R                        i++;" j' o) I( c# X5 z. A5 d" ]# f
                        k++;
8 j4 @" c/ w. w1 N' ^; d# f                        if (k == n)
# ]. I# ?2 \* }: P9 ~/ A6 G3 I5 h                        {; H3 m( T2 q6 \  j& z1 O
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了+ m* q! S! O( Y8 x5 @
                            k = 0;( S0 y5 ]! e( z5 S) ]
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
" s! [/ q, Y6 J& e                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
+ e- B7 g. j) O' A                        }
4 Q0 A9 z+ q" @+ @7 U                        else//输出暂时还没有改变数组元素的值+ m$ V, s& [$ y0 i& m$ C
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
4 C: \% m/ K: Q* J& l9 N) s, a                    }; D  ]& P. n4 u7 i% k  T9 M+ ]
                    else
, D" D. \/ L) m3 j                        i++;//数组元素为0,直接跳过,不计数。。。
, ~7 d: u. p& F                }0 x2 q; Z- H; U+ c) E" K

# l+ E8 @6 a# j4 E/ D; v
, c, H; N- n9 [            }//结束while循环" v' ^1 P0 t2 [1 l% d4 U
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 i2 ~9 n" o& ?' q. Z
           + f, c( N1 z7 I- l0 a8 u& R' U
                if (numw[i] != 0)1 k4 l  A& ^, m' o# p8 D4 i2 J
                    Console.WriteLine(numw[i]);" J% g8 P- _: z# ?5 d& w1 U2 H
           ( k4 t( n0 q5 U' e+ Y& ]# ^9 U; k( K
            Console.ReadLine();
( O1 @% ^0 {. `3 O/ y- ?        }
8 v# d' h  U* ?    }; x/ j  C  a6 m& M1 J$ D
}
( e  ~; T7 v. F. v  y) ^! q
小甲鱼最新课程 -> 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-2-18 23:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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