鱼C论坛

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

猴子问题

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

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

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

x
大家好!
2 h' Y* r9 O9 q0 c这几天我在忙着编一个问题,我用了一种方法编出来!
" n. R# M1 t1 }5 U但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
* o" t9 L3 F9 \, D4 h9 X注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
; q! v  }( w. m
" `) ?5 ?# [+ a- L- N1 D- y2 r" ]0 O& Y; L8 T9 `
                            题目
7 k1 G0 ~! d# n4 ~. O# h# w山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。# D; v) e/ T1 j( M1 u
第一种方法:利用循环链表8 o. K1 U9 i' g
#include<stdio.h>
  W: U0 V2 ?5 W4 D  v7 S& g% d#include<malloc.h>0 o: y: l& N8 P: e
#define M 8            //共有8只猴子
  S* i' O. m0 k2 f, a5 @#define N 3            //数到3只时退出第三只
$ |" x$ m! ?: W& `$ ~typedef struct monkey
1 X( M3 D' V3 F6 X{int number;% S5 ^5 C: v) N
int flag;
/ ^& [' i/ r' h# U8 \struct monkey* next;* b' F  g6 [6 C8 B  q/ O2 N
}MONKEY;+ j5 x: j8 k" j* w' j  N5 D
main()/ m2 z! t  h6 _2 }( I
{ MONKEY *head=NULL,*p,*s;
" z! u; p" K/ Z7 ?8 {6 q1 o  int i,sum=0,count=0;
; A+ T9 @) b7 o  clrscr();              //清屏
' A( V$ K% y0 ^% g% r  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存9 B. B( u- {2 P8 y) ~! w
  p->number=1;p->flag=1;
1 ?2 C, G& h: I8 ?% ~! a, |4 E$ y  p->next=head;) ~! \! G8 d5 A- K7 l
  head=p;$ Q- H4 f* m; K) u
  for(i=2;i<=M;i++)  j* s- l3 N  [
    { s=(MONKEY *)malloc(sizeof(MONKEY));
0 E$ f/ p' z, V$ m; J- D5 K$ l% p     s->number=i;s->flag=1;7 V/ u2 o  z9 \" O3 R$ |7 e1 v8 W
     s->next=head;
$ M+ V2 l$ ]) F0 r4 r8 H& V+ \     p->next=s;p=p->next;
( _3 Q& G5 \9 d8 D4 s) \    }
$ s. L( }  v1 f) H: Q0 @    p=head;
) X" b, r7 k: [   for(;;)
7 k! w2 a+ b0 n8 Q$ n    {if(p->flag==1)5 U3 s8 U! x/ e  X+ k
       count++;
1 T8 }7 b( i5 p* c+ o, ~, M9 U     if(count==N)
) A$ a. ^, h2 I) `" K% P& [        {p->flag=0;
8 W" q/ w5 W$ @6 C7 Z0 I         count=0;& C9 \* C7 m) X! Z+ k# w
         sum++;}
! Y# D0 q. V/ `4 ~4 [3 n     if(sum==M-1), U5 y# F- J' U& e' B
        break;7 Z: x/ y# O' ^
     p=p->next;* a2 Y" n% T, }! @% u' m
    }
) Y+ i7 a5 w) n: p7 T8 ^    p=
% U# `( K- F8 B' I8 V* U3 O* }0 j    head;* A! ]$ V, w- c+ \' A8 z& ^
    for(i=1;i<=M;i++)
% T5 |( ^! ^7 s% V. i    { if(p->flag==1)
" j  n9 w0 J+ u9 [        printf("\t%d",p->number);& \/ P& W. Q" r0 ]/ C2 {4 l' Y
      p=p->next;
& i# Z4 N. F1 J# i. ]7 u; x/ r    }
1 o: `5 F& }' I, C- Q1 [) a9 ?$ ?# L3 k/ v6 h3 R: `( j9 Z0 P3 G$ R

* c3 t5 G! k1 ?% M! d0 \
# I% y) v8 o7 X6 b" S. p}
2 l2 x" I* l  W7 B2 z, K- y
第二种方法:数组
5 L* j+ z9 `4 O# r: j: {. s: q#include<stdio.h>* i% N% g# h+ X. `
#define M 8
- I' {6 F4 ^& b( Jstruct monkey
* b! u, C3 ~8 Z) R3 k% X& B( H0 r  h{int number;
5 b( [; w4 C5 ~: K. ~) \int nextp;
! N; O, q7 c# J3 f' I+ }0 _' k}link[M+1];
! Q: u  U* ?% C* {2 D
  m1 D3 v0 ?7 O8 Bvoid main()9 _5 L. c7 o" P* K( e+ ~( A/ U
{int i,count,h;+ L, i! Z* v3 L
for(i=1;i<=M;i++)
7 j. S: d- e2 ?$ o3 Q{  if(i==M)/ M8 K6 g! E7 ^2 \5 q4 B7 e0 g
   link[i].nextp=1;
/ I- ^' r; l, P/ V   else
5 r( i5 Y, x& j4 S+ {3 T   link[i].nextp=i+1;
% D" B/ j/ }2 F, t+ ~% _" D6 X  link[i].number=i;
/ c( G- n; ?2 @}8 |+ P: A# @8 Z4 n
printf("\n");/ |( h" N8 a% e+ q. ]! {
count=0;
/ o+ v4 M  I& N) g4 Ch=M;7 r! k" \: J4 w! l# S
printf("依次退出的猴子: \n");
: L9 f7 P- s/ P5 W+ W. ^while(count<M-1)
6 z( ]9 k4 n% G$ `) T' N0 ]{i=0;
7 V% w3 k0 |5 B( nwhile(i!=3)
" @& n9 k: A3 t$ J. i{ h=link[h].nextp;/ h$ i9 Q  i* q( w7 T0 Q
   if(link[h].number)
: S3 k3 Z0 i% ?% F2 w. Q8 B" m     i++;}
+ H6 w7 j, Z3 f# q$ t5 U' l* h/ i4 h* {  T+ {# Z  i
printf("%4d",link[h].number);! a8 @  ?* w  Z8 M
link[h].number=0;! q: [! U) G% n! W
count++;
: d2 ^  X3 a$ Y/ L  K}
, d9 s' n4 j$ l) n, c& d2 ^. H2 T/ l5 L- }. D+ ?+ d2 g
printf("\n大王是:");/ X2 @' D& [3 W8 s7 a8 H
  for(i=1;i<=M;i++)
7 _! F3 p( Q( x$ G0 c$ p1 ^  if(link[i].number)
1 L. U% ]& k, @  r7 `' L, Y0 y    printf("%3d\n",link[i].number);6 T* k% n& y( t' p$ v

& A( s+ r' g; c- h  d" n! f6 J5 k/ K$ m5 i$ ]; n
}

$ W/ Y  G5 b0 u$ \9 e. E第三种是普通方法for循环
7 r8 v; U# F% D, d# N% M& P" }
#include<stdio.h>( E: H9 [" ?8 p9 f& `+ r
void main()! s4 {" J7 a, ]* u6 r
{ int i,k,m,n,num[50],q,*p;3 c6 J& w" ^( Z( R$ l5 R
    clrscr();
# l( O' n) Q+ W8 G) {   printf("input number of person: n=");
, ~2 ?8 ]0 c- g  t  [    scanf("%d",&n);
. i. i& o3 p; k1 `! t' H, uprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只/ g9 a! k! @* R7 f
    scanf("%d",&q);
7 `1 n/ b4 \" }4 O   p=num;
7 Q% b5 W* Y! ~* d" d; K$ `, v' @4 L  for(i=0;i<n;i++)2 `" I+ o% Y* s- X& m
    *(p+i)=i+1;8 f+ ]" R/ p7 I' H
   i=0;
4 z8 Q" U: R$ H   k=0;3 o: u+ z/ ]' g
   m=0;
& g8 o$ W: H/ M0 n' M" ?3 A  while(m<n-1)
  _% ]; b2 h( L  n; |. V   {if(*(p+i)!=0) k++;
& E, N. s9 x. O3 U- _) u, z     if(k==q)
, {1 E- c5 p5 o1 M2 ?      { *(p+i)=0;4 w9 H# B: Y! A# D1 N
        k=0;
* d  d0 i5 M* t' {4 D        m++;' c8 s# o( r0 U
      }
6 q$ f: R+ I* e/ `0 L    i++;0 ?% y1 c& o8 O  \: l! S2 g; c8 e
    if(i==n)i=0;
/ u8 `+ I% Q7 _) _( g   }
- N5 r- g5 w7 L7 [9 s  while(*p==0)p++;: A( J/ ]" y; Z1 L0 {
    printf("The last one is NO:%d\n",*p);, T/ q. H4 S0 Z& |- E' Q
     getch();
9 b) ?. R! U" S
9 O+ g1 ^! H; N6 k' G' E+ J}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;  f) N- f' `, z: b
namespace 又费马达又费电2 W' n( Q7 N: |6 c- A4 @$ |1 f7 i+ \
{
9 R0 K% n$ s* c5 J3 I% @0 T    class Program. f( S6 A7 e. v! G0 p0 H8 A
    {) E* U2 ?. W* H1 V5 H8 i/ b! ~
        static void Main(string[] args)
4 q5 l: v0 W" E$ h2 S        {
( g; \. r( u, P$ R            int m, n;
4 ?9 M5 S4 D8 t) W! P: p' W& E' [            Console.WriteLine("请输入数组长度");. p) _. E# p9 k% a% \% d
            m = int.Parse(Console.ReadLine());//m为数组的大小
. H* u$ P, @  l            Console.WriteLine("请输入要截取数字的大小");% H# j; j" a% B: w/ H+ h
            n = int.Parse(Console.ReadLine());4 A. S+ }5 A  p
            int [] numw=new int
, _. {4 O/ f4 Y
" `3 h7 Q% m; A4 m&shy;&shy;&shy;;: f+ j3 Z& \1 H- B
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数2 W4 [( Y7 [( U
            {5 Q6 x  f# h' |6 I* j/ {+ K
                numw[j - 1] = j;
2 b% I7 c' @# H. M            }4 m" K. H! i% y) ?; [
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!6 |8 h6 W- q: I: ^. v, L- b
            while (d != m - 1)
0 E- {) R/ u3 w  m            {
2 ?/ Y( t5 _; u                if (i == m && d != m - 1)4 I" @! `8 D/ h; j; Q2 i+ @
                {7 X+ B" d  E7 \9 a1 v
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!' L7 m6 W3 c0 P/ n
                    continue;; }7 I4 X, O" p$ n5 J& r. g0 r+ o
                }
; ?' [( ~; U0 @9 F. c: G                else1 r* i  b0 i5 c6 W' y
                {
. X% g6 @! ]$ l; l2 v/ V                    if (numw[i] != 0)
. {  ~% d) e5 \6 [* L                    {9 @" E+ V$ X  i! a. V+ K$ C
                        i++;
/ s4 o5 k. A. D% p& F" U                        k++;0 U: S3 k2 ]7 ~. L0 v
                        if (k == n)
8 J$ }5 d* L7 r5 X                        {
9 v* B5 {" z0 e9 b8 ~9 ~) r" B8 N                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& ?5 p* Q- ?+ {4 h' f  J4 k$ V
                            k = 0;5 y1 u& r7 x4 {! G% v: a
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1" z9 t. [( F& d7 f, L3 x
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% Y- P# H" s6 K5 ?" L+ O6 V                        }
+ H* E! Z- R7 W$ S. Y- g                        else//输出暂时还没有改变数组元素的值
$ c$ W  F& `5 c0 P& f% g                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( `& N8 T4 ]# C6 U' N                    }
4 D' X9 G, E1 }5 @, Q2 D                    else
( e$ S, ?2 `7 U6 U4 \/ [                        i++;//数组元素为0,直接跳过,不计数。。。
) n% g6 |( o! e6 o                }
* i1 I$ R1 q- Q * P% i; b2 S( V- o

* `! A! Q6 `: A, `            }//结束while循环+ H3 |1 g$ }6 l% o0 S! ?
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦2 f2 y% @" U; x/ Y$ M
           
" L# O3 ^7 Y" [# x3 u                if (numw[i] != 0)9 {6 D  a* B# v0 m9 g! w
                    Console.WriteLine(numw[i]);0 o, f4 P: \2 w7 Y
           
0 ]) ~, Y9 R! A6 o& s, Y. |  J+ m            Console.ReadLine();
- b) ^& L5 P" u. U        }) x# A6 g4 z6 \1 E" i5 u* M0 u. Y
    }0 ]4 ~6 f6 T2 @0 S
}' {; m) N4 V! h8 K6 ^
小甲鱼最新课程 -> 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-6 19:14

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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