在大會遞歸解決楊輝三角（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）

回答

相關問題