约瑟夫环的C语言和86/88汇编非递归算法

简介: 约瑟夫环的C语言和86/88汇编非递归算法

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。

我这个解决方案是,从1到n进行编号,打印出这些人的编号的出列顺序。

我是第一个发表对约瑟夫环的非递归算法(采用数组实现),发表时间是2006年6月。是对一个2004年的一个百度提问的解答。现在已经找不到那个帖子了。当时我给的结解决方案是用宏制定输入的人数和报数上线。

约瑟夫环的数组实现方法,虽然代码比代码多些,但是很好理解,并且理论上的解析范围比递归算法大的多(像汉诺塔问题用递归,达到63层跌代以上程序就跑飞了)。现在N多人都是改编的我的方案。

C语言实现约瑟夫环:

/***********************************************************

该程序是用C语言实现约瑟夫环的高效算法,它比链表有更高的空间和时间效率。

但它只支持最多人数为128人,若想实现支持更多人数只需要修改数组a的大小。

***********************************************************/

#include<stdio.h>
main()
{
    int a[128],b[128];
    int i,code,k,m,n,s,t;
    printf("输入初始报数上限值m:");
    scanf("%d",&m); 
    if(m <= 0)
    {
        return;
    }
    printf("输入人数n:"); 
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&code); 
        b[i]=code;
    }
    printf("指定开始报数人的编号t:");//第一个参照人的编号为1
    scanf("%d",&t); 
k=0;
    for(i=t-1;i<n;i++)a[k++]=b[i];
    for(i=0;i<t-1;i++)a[k++]=b[i];
k=0;
    while(n!=1){
        s=m%n;
        if(k!=0)s=(s+k-2)%n+1;
                    printf(" %d ",a[s-1]);
            for(i=s-1;i<n-1;i++)a[i]=a[i+1];          
    k=s;
    n--;
    }
    printf(" %d ",a[0]);
}

汇编实现:  这个汇编的方案我当时写了没有发表,相信没有其它人比我先发表这个方案吧!本方案已经运行测试。
;本程序是用汇编语言实现约约瑟夫环
;它最大支持255人的报数和人数
;它的密码要事先要在数据段初始化
;它的例子是从第一个报数为顺序进行密码编码的,当然可以自己编码
;认数和报数要事先要初始化
;它支持在DOS下运行并显示结果
;软件需求:LINK.EXE和MASM.EXE
          M1 EQU 6                ;初始报数上限值m:
          N EQU 6                 ;人数n:
DATA SEGMENT
SOURCE DB 01H,02H,03H,04H,05H,06H ;对应人的密码
RESULT DB N DUP(0)
M      DB 00H                     ;输出控制数
M2     DB 00H                     ;输出数据区指示变量
DATA ENDS
SSEG SEGMENT PARA STACK 'STACK'
DB  256 DUP(?)
SSEG ENDS
CODE SEGMENT
      ASSUME CS:CODE,DS:DATA,SS:SSEG,ES:DATA
START:PUSH DS
      XOR AX,AX
      PUSH AX
      MOV AX,DATA
      MOV DS,AX
      MOV ES,AX      
      MOV DH,0                     ;k=0
      MOV DL,N
      CMP DL,1
      JZ LOP2                     ;while(n!=1){
LOP1: MOV AL,M1                    ;s=m%n
      CMP AL,DL
      JB LOP4
LOP3: SUB AL,DL
      CMP AL,DL
      JNB LOP3     
LOP4: CMP DH,0            ;if(k!=0)s=(s+k-2)%n+1
      JE  LOP5
      ADD AL,DH
      SUB AL,2    
      CMP AL,DL
      JB LOP6
      SUB AL,DL
LOP6: ADD AL,1
LOP5: MOV AH,0 
      MOV CL,AL         ;CL---s
      DEC AL            ;AL---s-1
      MOV BX,AX
      MOV AL,SOURCE[BX] ;printf(" %d ",a[s-1])
      MOV BL,M2
      MOV BH,0
      MOV RESULT[BX],AL
      INC BL
      MOV M2,BL
      MOV AL,CL
      SUB AL,1
      MOV CH,AL        ;for(i=s-1;i<n-1;i++)a[i]=a[i+1]
      MOV AL,DL        ;AL--n
      SUB AL,1         ;AL--n-1
      CMP CH, AL       ;CH--i=s-1     
      JNB LOP7
LOP8: MOV AL,CH
      MOV AH,0
      MOV BX,AX
      MOV AL,SOURCE[BX+1]
      MOV SOURCE[BX],AL    
      INC CH
      MOV AL,DL
      SUB AL,1
      CMP CH, AL      ;i<n-1
      JB LOP8
LOP7: MOV DH,CL                    ;k=s
      DEC DL                       ;n--
      CMP DL,1
      JNE LOP1
LOP2: MOV BX,0
      MOV AL,SOURCE[BX]             ;printf(" %d ",a[0])
      MOV BX,N-1
      MOV RESULT[BX],AL
      LEA DI,RESULT
      MOV M,N
LOP0: MOV AL,[DI]
      AND AL,0F0H
      MOV CL,4
      SHR AL,CL
      CMP AL,9
      JA X1
      ADD AL,30H
      MOV BL,AL
      MOV AH,02H
      MOV DL,BL
      INT 21H
      JMP X2
X1:   CMP AL,61H
      JA X5
      ADD AL,40H
      SUB AL,09H
      MOV BL,AL
      MOV AH,02H
      MOV DL,BL
      INT 21H
      JMP X2
X5:   ADD AL,20H
      MOV BL,AL
      MOV AH,02H
      MOV DL,BL
      INT 21H
X2:   MOV AL,[DI]
      AND AL,0FH
      CMP AL,9
      JA X3
      ADD AL,30H
      MOV BL,AL
      MOV AH,02H
      MOV DL,BL
      INT 21H
      JMP X6
X3:   CMP AL,61H
      JA X4
      ADD AL,40H
      SUB AL,09H
      MOV BL,AL
      MOV AH,02H
      MOV DL,BL
      INT 21H
      JMP X6
X4:   ADD AL,20H
      MOV BL,AL
      MOV AH,02H
      MOV DL,BL
      INT 21H
X6:   INC DI
      DEC M
      JNZ LOP0
      RET
      CODE ENDS
      END START

我解决约瑟夫环的非递归算法的时间见图片:

我做的再window xp下运行我的汇编程序是在我2005年上学时做的,幸亏当时写了操作手册,不然现在我还运行不了呢!修改操作手册在window7(64位操作系统)上操作成功。

运行结果如下:

该问题的代码运行操作见文章:86/88汇编代码的运行调试 http://blog.csdn.net/jia12216/article/details/46895619

三级pc上机试题的可运行代码资源包的下载地址是:http://download.csdn.net/detail/jia12216/8902455


目录
相关文章
|
1天前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
11 7
|
9天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
9 0
|
9天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
15天前
|
算法 搜索推荐 C语言
C语言中的经典算法实现
C语言中的经典算法实现
19 1
|
23天前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
15 1
C语言数据结构算法,常用10种排序实战
|
26天前
|
算法 C语言
KMP算法(C语言实现)
KMP算法(C语言实现)
21 0
|
1月前
|
算法 C语言 人工智能
|
1月前
|
算法 C语言
【C语言】求最小新整数(贪心算法)
【C语言】求最小新整数(贪心算法)
17 1
|
1月前
|
算法 C语言
C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
C语言易混淆、简单算法、结构体题目练习、常见关键字总结
|
1月前
|
算法 编译器 API
C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
C语言易混淆、简单算法、结构体题目练习、常见关键字总结