在大会递归解决杨辉三角（NCK）

我目前坚持从组合问题得到了答案。我的basecase工作得很好。我认为问题在于评估组合（n-1，k），然后评估组合（n-1，k-1）。在大会递归解决杨辉三角（NCK）

这里是我的代码：n和k是从用户输入。

sub esp, 2 
push word[n] 
push word[k] 
call combi 
pop word[ans] ;store yung combi value sa ans 

;convert to ascii string value 
add word[ans], 30h 

;print answer 
mov eax, 4 
mov ebx, 1 
mov ecx, ans 
mov edx, 2 
int 80h 

jmp exit 


combi: 
    mov ebp, esp 

    mov ax, word[ebp+4] ;ax = k 
    cmp [ebp+6], ax  ;if (n==k) 
    je basecase 

    cmp word[ebp+4],0 ;cmp k = 0 
    je basecase 

    ;combi(n-1,k) 
    mov ax, [ebp+6] ; ax = n 
    mov bx, [ebp+4] ; bx = k 

    dec ax ;n-1 

    ;execute again 
    sub esp, 2 
    push ax 
    push bx 
    call combi 
    pop cx  ;stores to cx popped value combi(n-1,k) 
    mov ebp, esp ;update pointers 

    ;combi(n-1,k-1) 
    push ax 
    dec bx 
    push bx 
    call combi 
    pop dx  ;stores to dx popped value combi(n-1,k-1) 
    mov ebp, esp ;update pointers 

    add cx, dx ;combi(n-1,k) + combi(n-1,k-1) 

    mov word[ebp+8], cx 
    jmp combi_exit 


basecase: 
    mov word[ebp+8], 1 

combi_exit: 
    ret 4

希望您的回应和出色的想法！谢谢！

来源

2017-11-18 Code Geek

[编辑]，添加上它是错的情况下，更多的细节，使这个[MCVE。使用调试器单步执行代码并查看寄存器，以便您可以按照预期方式查看停止工作的位置。 –

虽然这个'add word [ans]，30h'显然是错误的。它只适用于一位数字。（请参阅[x86标记wiki]（https://stackoverflow.com/tags/x86/info）中的多位数字FAQ条目。）为什么在32位Linux进程中的任何地方都使用16位操作？使用32位操作会更有效率。 –

不能编译，缺少一些部分（如数据定义）。 – Ped7g

要解决你的递归的combi:的中间部分有一个问题：

... 
    call combi 
    pop cx  ;stores to cx popped value combi(n-1,k) 
;*^this freed the allocated space for result 
    mov ebp, esp ;update pointers 
;* not needed, as you will not use EBP right now, and next call destroys it 

    ;combi(n-1,k-1) 
    push ax 
;*^pushing first argument, but no stack space reserved for result 
    dec bx 
    push bx 
    call combi 
    ...

为修复你可以调整部分：

编辑：这不会为2+正常工作深递归，因为你需要不保留寄存器，整个递归结构需要更多的关心，我会简单地选择在第一位置更简单的设计，重写一遍，不是解决这些小问题。这个“修复”至少可以阻止部分违约行为。

... 
    call combi 
    mov cx,[esp]  ;stores to cx value combi(n-1,k) 
;*^keeps the stack space reserved (not popping) 
    ;combi(n-1,k-1) 
    push ax 
    ...

当然还有其他问题，您的输出是只为单个数字是正确的，但只是搜索堆栈溢出，tag [x86] info对于那些不打算在这里重复。

顺便说一句，这IMO从不幸的过于复杂的使用堆栈茎，你有你为什么遵循这样复杂的调用约定一些特别的原因吗？如何在自定义快速调用类似的参数和结果寄存器？它的性能也更高，但对我个人而言，跟踪事情并正确处理堆栈也更容易。如果我会尝试......我可以在以后的版本中添加我自己的变体。

编辑：

文件：用寄存器调用约定全面工作示例so_32b_pascal_triangle.asm

section .text 

global _start 
_start: 
    mov  ecx,5  ; n 
    mov  edx,2  ; k 
    call combi 
    ; return to linux with sys_exit(result) 
    mov  ebx,eax 
    mov  eax,1 
    int  80h 

; ECX = n, EDX = k, returns result in EAX, no other register modified 
; (_msfastcall-like convention, but extended to preserve ECX+EDX) 
combi: ; c(n, k) = c(n-1, k-1) + c(n-1, k), c(i, 0) = c(i, i) = 1 
    test edx,edx  ; k == 0 
    je  .basecases ; c(i, 0) = 1 
    cmp  edx,ecx  ; k == n 
    je  .basecases ; c(i, i) = 1 
    ; 0 < k < n case: 
    dec  ecx   ; n-1 
    call combi  ; EAX = c(n-1, k) 
    push esi 
    mov  esi,eax  ; keep c(n-1, k) in ESI 
    dec  edx   ; k-1 
    call combi  ; EAX = c(n-1, k-1) 
    add  eax,esi  ; EAX = c(n-1, k-1) + c(n-1, k) 
    ; restore all modified registers 
    pop  esi 
    inc  ecx 
    inc  edx 
    ret     ; return result in EAX 
.basecases: 
    mov  eax,1 
    ret

编译+运行+显示结果：

...$ nasm -f elf32 -F dwarf -g so_32b_pascal_triangle.asm -l so_32b_pascal_triangle.lst -w+all 
...$ ld -m elf_i386 -o so_32b_pascal_triangle so_32b_pascal_triangle.o 
...$ ./so_32b_pascal_triangle ; echo $? 
10 
...$

编辑：

而对于我自己的好奇心，试图把它从C-ISH C++代码（验证fastcall约定按预期工作需要与C/C++的互操作性，即使）：

该so_32b_pascal_triangle.asm文件具有相同combi:代码，但开始时修改（添加全球，除去_start）：

section .text 

global combi 
; ECX = n, EDX = k, returns result in EAX, no other register modified 
; (fastcall-like convention, but extended to preserve ECX+EDX) 
combi: ; c(n, k) = c(n-1, k-1) + c(n-1, k), c(i, 0) = c(i, i) = 1 
    ...

文件so_32b_pascal_triangle_Cpp.cpp：

#include <cstdio> 
#include <cstdint> 

extern "C" __attribute__ ((fastcall)) uint32_t combi(uint32_t n, uint32_t k); 

int main() 
{ 
    for (uint32_t n = 0; n < 10; ++n) { 
     printf("%*c", 1+2*(10-n), ' '); 
     for (uint32_t k = 0; k <= n; ++k) { 
      printf("%4d", combi(n, k)); 
      // 4-char width formatting - works for 3 digit results max. 
     } 
     printf("\n"); 
    } 
}

生成+测试：

$ nasm -f elf32 -F dwarf -g so_32b_pascal_triangle.asm -l so_32b_pascal_triangle.lst -w+all 
$ g++ -std=c++17 -c -m32 -O3 -Wall -Wpedantic -Wextra so_32b_pascal_triangle_Cpp.cpp 
$ g++ -m32 so_32b_pascal_triangle*.o -o so_32b_pascal_triangle 
$ ./so_32b_pascal_triangle 
         1 
         1 1 
        1 2 1 
        1 3 3 1 
       1 4 6 4 1 
       1 5 10 10 5 1 
      1 6 15 20 15 6 1 
      1 7 21 35 35 21 7 1 
     1 8 28 56 70 56 28 8 1 
     1 9 36 84 126 126 84 36 9 1

来源

2017-11-18 12:36:50 Ped7g

在大会递归解决杨辉三角（NCK）

回答

相关问题