Cần giúp đỡ thuật giải đệ quy của bài số đảo ngược

#1

Ví dụ số 12345 chuyển qua thành số 54321.
Chứ cout ngược từng số thì em làm được rồi ạ.
Em cảm ơn!

#2

gợi ý lấy số đó chia 10 xuất dư và return số đó chia lấy nguyên!

2 Likes
#3

Mã giả đây, cũng chả biết mình đang code ngôn ngữ nào nữa :confused: Nói chung là khi chuỗi thứ nhất còn ký tự thì bốc cái ở đầu tiên cho lên trước chuỗi thứ hai, khi nào xong thì in chuỗi thứ 2 ra.

string[] step(string[] input)
{
    if (input[0].length == 0)
        return input;
    input[1] = input[0][0] + input[1];
    input[0] = input[0].subString(1, input[0].length - 1);
    return step(input);
}

void printReverse(int input);
{
    string text = toString(input);
    cout << step(new string[]{text, ""})[1];
}
5 Likes
#5

ab = a * 10^1 + b * 10^0
ba = a * 10^0 + b * 10^1
Viết đệ quy thì nên bắt đầu từ base case. Base case thường đơn giản và để kết thúc đệ quy.
Bài này thì mình cứ lấy số đơn vị nhân với 10^(số lượng chữ số - 1) rồi cộng dồn lại với kết quả của lần đệ qui trước đó thôi.

// countDigit(12) == 2
int countDigit(int x) {
    return ???
}
int _reverseInt(int x, int numberOfDigits, int reversedInt) {
    //base case
    if (numberOfDigits == 0) {
        return ???
    }
    return _reverseInt(???, ???, ???);
}

int reverseInt(int x) {
    return _reverseInt(x, countDigit(x), 0);
}
2 Likes
#6

Không dùng cout cho bạn.
Bạn phải viết thêm một hàm demChuSo để đếm số các chữ số (viết thêm hàm tính lũy thừa thì càng tốt)
Hàm đệ quy bằng C/C++:

int daoNguoc(int N)
{
    if(N == 0)
         return 0;
   
    return (N % 10) * luyThua(10, demChuSo(N) - 1) + daoNguoc(N / 10);
}

edit: Xin lỗi, nhầm logic, điều kiện phải là if(N == 0) return 0;

#7 
int _reverse(int x, int rev) {
    if (!x) return rev;
    return _reverse(x/10, 10*rev + x%10);
}

int reverse(int x) {
    return _reverse(x, 0);
}
4 Likes
#9

Em cảm ơn các anh, cô em sửa theo cách này cũng đơn giản dễ hiểu ạ:

int deQui(int n, int sdn)
{
	if (n == 0)
		return sdn;
	else
	{
		sdn = sdn*10 + n%10;
		return deQui(n/10, sdn);
	}
}
4 Likes
#10

Thế này là ổn nhất :smiley: đệ quy đuôi.

2 Likes
#11

Thường thì nên viết đệ qui kiểu tail call. Bạn search thử tail call optimization xem.

1 Like
#12

Mình cũng nên viết thêm 1 hàm nhận số đó và trả ra số đảo ngược của nó. Như vậy thì hàm sẽ dễ dùng hơn

#13

@Huy_Nguyen1 Cảm ơn bạn, chỉ tham khảo vậy thôi chứ mình không thích đệ quy cho lắm, viết code thì nên tránh đệ quy.

#14

:thinking:

#15

Tùy vào vấn đề, nhưng thường thì cách viết đệ quy thường khó hơn, đệ quy chỉ có tác dụng trực quan hơn trong một số vấn đề, nhưng để viết ra một giải thuật đệ quy thường tốn thời gian suy nghĩ hơn cho nhiều người. Nếu vấn đề có thể giải quyết đơn giản không cần đệ quy, không lý gì lại đi ngồi nghĩ cách viết đệ quy, và không phải ai cũng có thể viết ra một giải thuật đệ quy một cách nhanh chóng được.

2 Likes
#16

Thực ra cái này mình nghĩ là do từ khi học mình học loop trước nên cách nghĩ của mình luôn hướng đến loop khi giải quyết 1 vấn đề. Chứ bt nếu ko phải functional programming language thì k ai lại học đệ quy trc cả

#17 
int Sodaonguoc( int n)
{
   int t=n%10;
     if(n>0)
    cout<<t<<" ";
   Sodaonguoc(n/10)
}
2 Likes
#18

chao ban, minh moi hoc nen khong hieu ro ve de qui, ban co the giai thich giup minh duoc khong a?

#19

Vui lòng viết tiếng Việt có dấu.

3 Likes
#21

  1. Tại sao bạn cần phải tạo biến tam trong khi bạn có thể gán thẳng sum = sum * 10 + n % 10?

  2. Bạn có thể bỏ biến toàn cục sum để xử lý hoàn toàn trong hàm Daoso được không? Hiện tại code của bạn sẽ gặp lỗi hàm Daoso không có giá trị trả về khi n > 0.

1 Like
#22 
#include<stdio.h>
int Daoso(int n)
{
    static int Tam = 0;
    static int Vitri = 1;
    if (n > 0) {
        Daoso(n / 10);
        Tam += (n % 10) * Vitri;
        Vitri *= 10;
    }
    return Tam;
}
void main(){
   int n;   printf("n=");   scanf("%d",&n);
   printf("In dao nguoc %d la:%d",n,Daoso(n));}
#23

Bỏ biến static đi bạn. Bạn đưa ra công thức truy hồi xem nào.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?