Hỏi bài tập đệ quy đếm số chữ số của số nguyên dương

#1

Em mới học đệ quy, thầy cho bài này thì phải giải đệ quy kiểu gì ạ, cách bình thường thì em làm được rồi ah!
Question: Hãy đếm số lượng chữ số của số nguyên dương n (dùng đệ quy)

1 Like
#3 
// pseudo
int count = 0;
function soChuSo(n){
  if (n<10) {
    return count++;
  }
  else {
    count++
    return soChuSo(n/10);
  }
}

đại khái là vậy, bạn check lại syntax & kết quả

1 Like
#5

Muốn giải được thì phải hiểu thế nào là đệ quy.

Phân tích bài này chút nè.

  • Đầu tiên phải tìm được điểm dừng của đệ quy.
  • Tiếp đến là tìm được công thức đệ quy.

Tìm điểm dừng của đệ quy

Muốn tìm được thì phải dựa vào trường hợp đơn giản nhất. Tức n chỉ có 1 chữ số. Hay điều kiện dừng là n < 10. (đề cho n dương)

Vậy là có ngay cái if đầu tiên.

    if (n < 10) return 1;

Tìm công thức đệ quy

Giả sử n có a chữ số. (a > 1)
Thì ta có [n / 10] có a - 1 chữ số.
Suy ra số chữ số của n là số chữ số của [n / 10] cộng thêm một.

Với [] là phép lấy phần nguyên.

Vậy là đã có được phần của còn lại của cái if ở trên.

    return 1 + F([n / 10]);

Code

#include <iostream>

int countDigits(int n) {
    if (n < 10 && n > -10) return 1;
    return 1 + countDigits(n / 10);
}

int main() {
    std::cout << countDigits(1234);
    return 0;
}

P/s: Bonus cho n âm. :stuck_out_tongue:

Mình góp ý cho bạn @DoTran1 chút xíu.

Bạn tích cực đóng góp cho DNH là tốt. Nhưng bạn nên đọc kỹ câu hỏi và suy nghĩ kỹ câu trả lời trước khi rep bài của một ai đó.

Còn nữa nếu bài đã có tag language của nó rồi thì bạn nên post code (nếu có) bằng ngôn ngữ mà chủ thread đã tag.

Với lại mỗi lần muốn sử dụng hàm soChuSo() của bạn lại phải đưa count về 0. Đó là chuyện phải làm bên trong hàm chứ không phải ngoài hàm.

P/s2

Đã lâu mình không post bài trên DNH. (do mải ôn thi. :stuck_out_tongue: :stuck_out_tongue: )

7 Likes
#6

thanks đã góp ý, tôi sẽ chú ý nhưng riêng trường hợp

thì tôi nghĩ code bằng ngôn ngữ nào cũng như nhau á, bạn ý cần giải thuật hơn là ngôn ngữ.
Tôi k biết c++, vậy tôi có cần lên mạng đọc syntax của c++ để viết cho bạn ý k?

uk, đúng rùi, tôi sai

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