Delphi课外练习题1---约瑟夫环(总结)

lvcaolhx

是一个数学的应用问题：

    已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，求剩下的最后一位？

要求：只能使用数组、字符串解决问题，不能使用指针，链表。
测试数据：
如：6个人，报数4，从3开始，最终为1
15个人，报数5，从5开始，最终为5
10个人，报数5，从1开始，最终为3

不完美的Delphi程序：
源代码
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Label2: TLabel;
    Edit2: TEdit;
    Label3: TLabel;
    Edit3: TEdit;
    Button1: TButton;
    Edit4: TEdit;
    Label4: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var
  sum,BaoShu,YuShu,i1,pose,CiShu,i2,i3:integer;
  i:string;
  a:array [1..1000] of integer;
  begin
  sum:=StrToInt(Edit1.Text); //该函数用于将“字符型”转换成“整数型”
  BaoShu:=StrToInt(Edit2.text);   //取报数值
  YuShu:=sum;
  pose:=StrToInt(Edit3.text)-1;
   i2:=0;       //初始化
   for i3:=0 to 1000 do a[i3]:=0;   //数组初始化
  while (YuShu>=1) do
  begin
  i1:=1;

         while (i1<= BaoShu) do     //报数循环变量i1从0开始循环
        begin
          i2:=pose+i2+1;
          if (i2>sum) then i2:=1;    //位置循环变量大于总数,则从1开始
          if (a[i2]=0) then i1:=i1+1;  //若位置循环变量所指的位置,其值为o,则报数循环增加一;为1则不增加
          pose:=0;    //开始报数位置只参加一轮循环
          end;
          a[i2]:=1;  //退出的位置
          YuShu:=YuShu-1;
          CiShu:=CiShu+1;
              end;
       Edit4.Text:=IntToStr(i2);
end;

end.

思路:1.总人数为m,则要循环m-1次
     2.报数超出总数时,得从头开始
     3.报数所指位置被淘汰时,报数继续而循环变量值不增加

[ 本帖最后由 lvcaolhx 于 2007-12-18 14:59 编辑 ]

iawen

大哥，我只会启动和退出Delphi啊

learnlife

给几组测试数据，我用“一维数组”结构写了一个算法，不知道对不对
这个是经典问题，再复杂一些就是每个人都存储一个密码值，每次从1开
始报数时，报的最大数在变化，以前我是用双向循环链表做的。

给几组测试数据吧，我看看是否正确。

learnlife

关于Delphi课外练习题1---约瑟夫环的程序
大家好，我是learnlife，写的不好的地方请大家多多指教。
楼主给出的以下三组测试数据：
6个人，报数4，从3开始，最终为1
15个人，报数5，从5开始，最终为5
10个人，报数5，从1开始，最终为3
均通过测试。

1. program Joseph;
   
2. 
   
3. {$APPTYPE CONSOLE}
   
4. 
   
5. uses
   
6.   SysUtils;
   
7. 
   
8. var
   
9.   a: array of integer;
   
10.   i,index,n,k,m,count: integer;
    
11. 
    
12. begin
    
13.   Write('输入约瑟夫环的总人数：');
    
14.   Readln(n);
    
15.   Write('输入报的最大数字：');
    
16.   Readln(m);
    
17.   Write('输入第一个开始报数的人的编号：');
    
18.   Readln(k);
    
19.   SetLength(a, n);
    
20. 
    
21.   index := (k mod n) - 1;
    
22. 
    
23.   for i := 1 to n-1 do
    
24.   begin
    
25.     while (a[index] <> 0) do
    
26.     begin
    
27.       index := (index + 1) mod n;
    
28.     end;
    
29.     count := 1;
    
30. 
    
31.     while (count < m) do
    
32.     begin
    
33.       index := (index + 1) mod n;
    
34.       if (a[index] = 0) then
    
35.       begin
    
36.         count := count + 1;
    
37.       end;
    
38.     end;
    
39.     a[index] := i;
    
40.   end;
    
41. 
    
42.   for i := 1 to n do
    
43.   begin
    
44.     if (a[i - 1] = 0) then
    
45.     begin
    
46.       Write('最后一位为：', i);
    
47.     end;  
    
48.   end;
    
49. 
    
50.   Readln;
    
51. end.

复制代码

[ 本帖最后由 learnlife 于 2007-12-12 12:09 编辑 ]

独晨

以前学的全还给老师了。哎。/:L

lvcaolhx

learnlife兄弟写得是passcal语言
看来对Delphi了解不多
现给出一个简单的Delphi程序
遗憾的是，不能在Memo中输出每次退出的人（Memo没弄懂）
哪位兄弟帮忙完成！




本来想做成图中的样子，水平不够呀！

[ 本帖最后由 lvcaolhx 于 2007-12-18 15:12 编辑 ]

pingan

什么时候开始教编程了，我可是刚学了第一课，只会打开和关闭DELPHI，别的什么都不会呀！

learnlife

呵呵，Delphi背后用的就是Pascal语言的升级版——Object Pascal语言，
lvcaolhx请看一下Delphi的背景。
我写的是控制台程序，在Delphi7下编译的。

liangwj888

勤奋才是硬道理
我试着用C试着编译了
还没成功~~/:L

xhpro

我成功用C编译了 但是D还没成功