鱼C论坛

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

猴子问题

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

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

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

x
大家好!; |1 M4 }) T/ O) D2 W% O: @3 _6 G
这几天我在忙着编一个问题,我用了一种方法编出来!0 [) c4 }8 B: i3 Q& A/ ~  F8 e( \  y
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
9 P5 B8 ~1 u" i( B: l3 v4 p$ f注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 2 X  n- A3 s0 F

; \$ f: \7 _# t; J$ @; Y. W5 |# \) T. ]$ |+ ]% v7 F+ {3 k0 R
                            题目, f6 m3 }8 j: W( {  I  j8 S
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
% x7 w5 W! g  X第一种方法:利用循环链表
2 E( h2 w8 l5 g#include<stdio.h>
+ z6 K& n  i; d( z, x#include<malloc.h>
) E$ j, l9 c+ b1 i+ r#define M 8            //共有8只猴子7 x( H, W5 B! D; V+ B. n1 s
#define N 3            //数到3只时退出第三只+ d' }& V, ]6 [' L! }  k  w' A
typedef struct monkey
* S( ]& }2 }/ V, ~' E4 `2 g4 B+ O{int number;4 n9 n+ v1 b6 d" w" ?
int flag;4 \# X9 \% s$ \; C
struct monkey* next;2 m' f$ h+ f  {4 ~; M/ q9 o- L+ K
}MONKEY;+ G+ F; R2 E4 |' B1 L
main()
: w* Q6 l( h. N7 s7 z6 [{ MONKEY *head=NULL,*p,*s;
# S" ~) K5 q" y- c$ J  int i,sum=0,count=0;% V4 l& M3 _* ]# `( ]: a( t/ M) O
  clrscr();              //清屏
8 ~/ q+ M2 J1 L! z# m; w  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
5 {' ^' S$ K! }+ c  p->number=1;p->flag=1;/ ?: A- [4 S* W. h' V
  p->next=head;+ u  u- ?7 f) @- a0 B  U; Y$ U
  head=p;
$ A% s/ a1 ^3 ^8 [$ `% X7 }9 e  for(i=2;i<=M;i++)7 L0 e( ?* w& L- K% e% e
    { s=(MONKEY *)malloc(sizeof(MONKEY));6 |; T4 W: q5 D; `8 b0 u5 I
     s->number=i;s->flag=1;4 p; B/ t6 N5 [/ J
     s->next=head;- v* x" H$ f! Z0 Q
     p->next=s;p=p->next;
1 J. }+ h  o3 a! f' @    }
0 I7 A0 B" n& T' p/ m    p=head;  G4 C% @  D" v" `" I& K
   for(;;); L* V; w" U2 g! S1 _: I
    {if(p->flag==1)
) j7 j* \9 o0 ?' g       count++;
. m7 I) U# d5 D" j  s5 R     if(count==N)
) q$ |4 c5 T( m9 \0 ^1 u) K        {p->flag=0;! {" k7 m# D2 H- `9 F4 ?; W
         count=0;
0 u) S' t& ~- E, S( v4 m( W         sum++;}# ?$ V' M! i3 ?0 a9 s. \4 p
     if(sum==M-1)
2 ^4 d! N# l. Q        break;
0 d/ l5 G" f1 K6 d8 D& i& j     p=p->next;8 s/ _) m) w7 U5 l3 p
    }6 f; c! _1 Y0 M7 X5 d4 z) n7 M9 J
    p=6 K9 T# `$ k' _1 l0 f
    head;. I/ A8 q( X( Y" g# J9 b4 Z
    for(i=1;i<=M;i++)
5 c" D3 F2 l8 W2 F' J3 x    { if(p->flag==1)
: |! B0 C# r2 y  E        printf("\t%d",p->number);2 ?# x$ a5 n! X' F& _, g
      p=p->next;
6 M) F+ M, e1 g+ z& D: \1 v9 Z    }& ^0 K& b) ~: l) y

6 c+ |4 Y2 r6 L1 H+ H% k( Z* R9 p1 S7 q( k6 n% b; s
. n% o/ G0 H9 a. T+ J
}
# i) n- e# K/ Z8 i
第二种方法:数组
6 L  k) q/ X7 O. A#include<stdio.h>4 c" `' G- ]4 J( l
#define M 8
  W5 M# X1 J$ Tstruct monkey
) z* }6 x- ^; ?" y7 K{int number;
" D5 Y0 u3 A& h7 p# Wint nextp;$ U' m& B( Z* W7 ^  L7 U
}link[M+1];0 i7 S! _  W2 i; W/ r. u/ T

; a& W8 [) p4 Z  p( f7 o/ O: Bvoid main()
: r2 m; D  O* x' r{int i,count,h;
& }5 k7 H0 f! d% E" \" o- q' Cfor(i=1;i<=M;i++)( m$ t4 q$ g) _4 i! c, y6 C- v/ I
{  if(i==M)" L% O5 ?: j4 K, n$ \' E
   link[i].nextp=1;9 k+ Q" n$ J% F. E
   else
: t, Y' U( l% X' O( d8 }3 `   link[i].nextp=i+1;- F7 [8 w. \1 }* V9 p/ `/ [, X* \
  link[i].number=i;$ \$ B. [4 B7 |' k
}
/ G) {. L  e8 C1 Z* }printf("\n");
# E( Y, Y5 B. u0 A, C6 W6 d! z$ xcount=0;
+ M& t5 d/ N) {, ?) ]h=M;5 D- N; T) u! B! c# W& i! M
printf("依次退出的猴子: \n");
/ g6 E6 A8 |: f; [+ V2 E$ Pwhile(count<M-1)0 C( j" s6 {0 e1 L+ W
{i=0;
; H/ V% r. x) o" N+ F& x. twhile(i!=3)
# ^* O/ e! ~1 {{ h=link[h].nextp;
, a/ R  w# G4 m& u1 e  G! D   if(link[h].number)
/ ~$ I  w- A) l4 ^; C& A- @     i++;}9 B/ Z& ~' h4 E" ]
1 M, M5 [' c2 k8 k8 j  V
printf("%4d",link[h].number);8 E6 e+ J" ^6 F! X9 T9 {: ?- z5 E1 B
link[h].number=0;' z0 W/ {+ l# h; H* |, K5 R& c
count++;4 ^) Z8 k- W( B9 n
}
& x+ R% y  S! ~( S0 T* n" _$ H- [3 ]2 I! P, u8 F6 U% U* |0 S
printf("\n大王是:");
- r* _/ T7 i8 E7 D8 B! _1 K  for(i=1;i<=M;i++)( y1 f9 x- f9 p, a
  if(link[i].number)
" M' A  J) S' e+ D- W    printf("%3d\n",link[i].number);
" M! z0 b8 V2 ~& A# {. C- `5 N8 Q& ^; n5 \; O# v
: `5 ^! K# U. o) _3 s* a
}

) A( X8 x7 m. m5 @+ h/ q- q, k第三种是普通方法for循环
: {6 @; b5 z/ l2 Y5 v
#include<stdio.h>. ]3 C" K) i/ D# N! h
void main()' \+ h. y( R9 {7 ?
{ int i,k,m,n,num[50],q,*p;
  _  M% c* l- J( q( o    clrscr();
: j2 ~8 ]) X+ s5 m3 ~+ _" i   printf("input number of person: n=");6 B6 \. r& q  n
    scanf("%d",&n);- U( W# d9 K, y, T
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只! c; @* I+ ]) U& I, o7 y5 R- h
    scanf("%d",&q);
( l* H1 f( g& N' P4 D& Y8 i   p=num;
1 O1 O, U! N2 ~4 T. f2 _/ h! x: n  for(i=0;i<n;i++)
' T& ]" T: r) K- \7 k% |    *(p+i)=i+1;5 I5 S" B7 p& h" v1 V  O3 ?6 h8 {
   i=0;
: ?) Q/ B- w3 p   k=0;6 w' P: p0 C7 Y2 J7 F2 f
   m=0;
; G7 {' O' `$ E  while(m<n-1)
! R3 _/ P: A! {+ {6 \  g  r& ]   {if(*(p+i)!=0) k++;
1 @# R. }8 q: b     if(k==q)
! T# k2 @4 \: }# B      { *(p+i)=0;4 a% B' F+ |2 H+ ?  ?  H/ B' R
        k=0;- u$ i, ?0 I; ?; d
        m++;
  G+ O4 b2 J! d2 @+ I6 a- e      }
! k' a( W  p+ v8 |3 M    i++;* U: I  R0 [, d3 Z# ~8 n
    if(i==n)i=0;  w/ Q) a. Z! d/ R7 r9 l# `4 Y& q0 K+ a
   }5 c( ]0 A+ b0 A6 i- k# R
  while(*p==0)p++;
9 C4 ]4 L& m. s# ^* R8 v    printf("The last one is NO:%d\n",*p);
  ~9 E8 h8 t9 T* [/ j) l     getch();. h5 K1 B- \$ O4 M9 r' I

! k( Q1 W6 L6 `}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;. @5 m+ h+ f. {8 R& X: _5 _5 I" E- B4 M0 C
namespace 又费马达又费电: d/ P8 s3 ^6 N2 s3 f
{6 o* Q+ b' X5 y
    class Program2 i: ~- Q! M( F2 b+ t) @
    {9 V3 f) S" V8 B; I
        static void Main(string[] args)0 y' d! Q$ V5 I+ G0 F
        {
4 H; F( J/ E9 B9 _            int m, n;
7 E" G- [! V9 G& ?) ]            Console.WriteLine("请输入数组长度");. q: I# y% ]6 Q
            m = int.Parse(Console.ReadLine());//m为数组的大小% P0 ]4 i( n; `+ M
            Console.WriteLine("请输入要截取数字的大小");' K( L  z' w, P$ O1 n4 }. `
            n = int.Parse(Console.ReadLine());
4 \  V% Z1 h- p' W/ |6 h            int [] numw=new int+ z. I1 E4 E% H
( z& p6 w' {: r% t$ H; `% t8 a
&shy;&shy;&shy;;: q( x, q; T4 U
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数+ p; }" A( o% L7 o& j4 q/ x% S
            {3 w0 R* u7 N7 s5 z
                numw[j - 1] = j;
' A2 Y9 Y- g" Q4 S0 \: u            }
9 Y% `5 q7 j4 \4 f$ ?% x            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!5 X+ Z0 B  }9 ?6 V
            while (d != m - 1)# n4 z' m/ a1 b* A" M/ n# X
            {
* D0 c% P; `4 z5 b! S                if (i == m && d != m - 1)' |1 ]3 {$ k) _! D7 C* \
                {" ?1 x/ ~. P& e8 P
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!* [) }( b9 I7 X3 w% R# s" U
                    continue;
7 l# S% I" n" C5 [7 L+ O9 M- S                }5 g1 v# F; V( R% f& E5 f: w: H
                else
8 Z) }3 X5 `7 }6 I  B' D3 a                {* t* V! b1 B+ D, b% j4 w
                    if (numw[i] != 0)
: v; y& B* N3 ?& \, R9 ]- n; |, b. P7 d                    {
! W; l$ Y  }2 F3 g# t                        i++;( J8 |% {9 x7 a
                        k++;
4 M! V: c4 y' l& J( a                        if (k == n)2 C; Q3 {! L8 w+ w2 b/ Q
                        {" a% z. Y% z( r! g
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了3 K8 S6 W3 Z' N& ^
                            k = 0;; b# R, t9 y! I9 S
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
2 g" o: p. ]4 p# H, H                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; N+ o0 p* T" Z& }9 H& ~
                        }" S$ x4 {% W- U: b! w2 }
                        else//输出暂时还没有改变数组元素的值+ r1 _( V2 z8 n
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 Y  Q' w2 i) B/ W4 [
                    }4 M# u7 u' ]; u/ p  }- ]5 G
                    else0 M4 e1 ^( ^/ l- D( t0 ?, J
                        i++;//数组元素为0,直接跳过,不计数。。。
, _3 z9 o* f: `% W5 y0 h1 y$ S                }1 e% R8 ~; i* E* V" y1 S

5 w" g8 Y" O. K: X+ t0 r5 r0 M2 b+ G3 |! S4 |# }
            }//结束while循环
1 T+ t! I- P) i4 ]0 r            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
+ e! j0 D2 }; T5 l% y9 R           
1 T9 O* C: W; G$ ~                if (numw[i] != 0)' v. j4 [# J: z  ]# F1 v
                    Console.WriteLine(numw[i]);2 l. e: N+ e! W% o. i% L3 d* u
           0 j8 S& q/ R+ g& l) N+ D
            Console.ReadLine();
" Q2 ^4 [% d8 {+ q        }. g* _! b% B- F
    }2 F/ h  Q$ u9 W. U" F4 d
}6 A6 s: H% }6 m" `' G! R6 O; S
小甲鱼最新课程 -> 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-6-24 12:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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