在大会递归解决杨辉三角(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
希望您的回应和出色的想法!谢谢!
答
要解决你的递归的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
[编辑],添加上它是错的情况下,更多的细节,使这个[MCVE。使用调试器单步执行代码并查看寄存器,以便您可以按照预期方式查看停止工作的位置。 –
虽然这个'add word [ans],30h'显然是错误的。它只适用于一位数字。 (请参阅[x86标记wiki](https://*.com/tags/x86/info)中的多位数字FAQ条目。)为什么在32位Linux进程中的任何地方都使用16位操作?使用32位操作会更有效率。 –
不能编译,缺少一些部分(如数据定义)。 – Ped7g