PDA

View Full Version : [C] Bài tập dùng đệ quy tính tổng các ước số của N



neverland87
12-03-2007, 08:51 AM
Bài này kid kid đố neverland, giải xong òi, có điều chắc là không hay lắm thì phải, thôi thì cứ post code cho mọi người tối ưu giùm mình


#include<stdio.h>
#include<conio.h>
int TongUocSo(int n,int i)
{
if (i==n) return 0;
else if (n%i==0)
{
return i+TongUocSo(n,i+1);
}
else
{
return TongUocSo(n,i+1);
}
}
void main()
{
clrscr();
int n;
printf("n = ");
scanf("%d",&n);
printf("\nTong cac uoc so cua %d la %d",n,TongUocSo(n,1));
getch();
}

kidkid
12-03-2007, 08:58 AM
Ặc ai biểu neverland post câu í làm gì ? Chẳng qua là có U nhờ giải nhưng bận quá , sẵn tiện mới bị neverland đố bài toán khó quá nên đố lại thấy giải xong thì nhờ post lên cho anh em cùng tham khảo .

Kiểu ni chắc phải xử riêng neverland mới được hèm .

neverland87
12-03-2007, 09:55 AM
Ặc ai biểu neverland post câu í làm gì ? Chẳng qua là có U nhờ giải nhưng bận quá , sẵn tiện mới bị neverland đố bài toán khó quá nên đố lại thấy giải xong thì nhờ post lên cho anh em cùng tham khảo .

Kiểu ni chắc phải xử riêng neverland mới được hèm .

Tặng kid câu này :
Thấy câu: "code dễ bất ghi" (code dễ quá không thèm ghi ra)
Lập trình thế ấy mới ...phi lập trình"

Bận việc nên không thèm làm, cấn cho neverland làm hử?
Cho kid bài này: dùng đệ quy tính tổng các bội số của N trong khoảng từ N --> N*3 . Tương tự như bài trên á, giải dùm neverland nhé (làm hổng được mới nhờ kid làm đó) ^ ^

Xcross87
12-03-2007, 12:57 PM
Từ cái code trên của Danh, pete sửa đề bài đi 1 tẹo . Viết 1 chương trình đệ qui tính tổng và tích các ước số của n, từ 1 ước số i cho trước .
Ví dụ : n = 64 , i = 32 : phép tính bắt đầu từ i = 32 -> i = n = 64 ;

neverland87
12-03-2007, 02:03 PM
Hix,với đề bài pete cho thì neverland phải làm thành 2 hàm:
- Tổng các ước số của n từ 1 số i cho trước: dùng hàm int TongUocSo(int n,int i) như ở trên á.
Rồi trong thân hàm main(): cho nhập n và ước số cho trước của n. Sau đó printf("Tong cac so cua %d tu uoc so cho truoc la %d la %d",n,i,TongUocSo(n,i));
- Tích các ước số cho trước của n từ 1 số i cho trước: tương tự dùng hàm int TichUocSo(int n,int i) thôi

Không biết neverland có hiểu sai ý pete không nữa? Và pete có cách nào chỉ cần xây dựng duy nhất 1 hàm TongTichUocSo(...) không?

kidkid
12-03-2007, 04:13 PM
Ặc không biết pete có ẩn í gì không chứ như thế thì dễ quá , bi giờ viết trong 1 hàm luôn thì cũng không khó , nhưng code lại dở ( vì đang chat hay vì mình dốt sẵn nhỉ ? ).

kid viết lại thử thế này :


int tongtich_uocso(int n,int i,char select[])
{

if(select=="tong")
{
if(i==n) return 0;
if(n%i==0)
return i+tongtich_uocso(n,i+1,"tong");
else
return tongtich_uocso(n,i+1,"tong");
if(select=="tich")
{
if(i==n) return 1;
if(n%i==0)
return i*tongtich_uocso(n,i+1,"tong");
else
return tongtich_uocso(n,i+1,"tong");

}

Viết thì được nhưng vấn đề cho hay thì để tối nay suy nghĩ coi .

Xcross87
12-03-2007, 04:43 PM
Thực ra thì không có gì là phức tạp đâu :D. Nếu các cậu hiểu ý mình thì nhận ra ngay. Thử nghỉ xem nếu có trường hợp nào làm chương trình bị crash không ? Vượt quá bộ nhớ hoặc giới hạn cho phép : Đệ quy rất hay nhưng rất chi là tốn tài nguyên. Nếu làm tích liêu có trường hợp nào vượt quá giới hạn cho phép của int kô? . Trong forum pete để ý thấy mọi người viết code không bao giờ tính đến trường hợp chương trình có lỗi không theo ý muốn. Điều này nghĩa là : chương trình code ngắn gọn, hay, chạy tốt là chưa đủ và cần có xử lý các tình huống khác. Ý mình chỉ có vậy thôi !

kidkid
12-03-2007, 04:53 PM
Đúng là thâm ý mà kidkid vừa mới viết bên kia , tích 2 số nguyên sẽ cho 1 số rất lớn , tuyệt pete phán câu này hay lắm :

chương trình code ngắn gọn, hay, chạy tốt là chưa đủ và cần có xử lý các tình huống khác

Xcross87
13-03-2007, 08:01 AM
Hix ... có gì đâu. Biết sao thì phát biểu vậy chứ pete trình C gà lắm :D

kidkid
13-03-2007, 12:35 PM
Hè hè ! Trong 4rum này mà Pete nhận mình gà thì lũ như kidkid đây đâu dám gọi là gà chứ !!!

javi
13-03-2007, 04:44 PM
Lần đầu tham gia diễn đàn. Có gì mọi người chỉ bảo thêm.

Ví dụ với N = 1000
N chia hết cho 2
Tìm ước số từ 501 (N/2 +1) là việc vô nghĩa

Suy ra: tìm ước của N trong vòng từ 2 đến sqrt(N), rồi giới hạn cận trên phải tìm thì giảm việc tính toán vô ích.

Ví dụ N = 909 thì chỉ cần tìm từ 3 đến 303

Nâng thêm 1 bước nữa:
. Khi (N%i)==0 thì công i và (N/i) vào.
. Vậy ta chỉ cần tính lặp đến sqrt(N)
. Order của chương trình sẽ thành căng bậc 2

neverland87
13-03-2007, 05:30 PM
Lần đầu tham gia diễn đàn. Có gì mọi người chỉ bảo thêm.

Ví dụ với N = 1000
N chia hết cho 2
Tìm ước số từ 501 (N/2 +1) là việc vô nghĩa

Suy ra: tìm ước của N trong vòng từ 2 đến sqrt(N), rồi giới hạn cận trên phải tìm thì giảm việc tính toán vô ích.

Ví dụ N = 909 thì chỉ cần tìm từ 3 đến 303

Nâng thêm 1 bước nữa:
. Khi (N%i)==0 thì công i và (N/i) vào.
. Vậy ta chỉ cần tính lặp đến sqrt(N)
. Order của chương trình sẽ thành căng bậc 2

Cám ơn bạn javi đã đóng góp ý tưởng cho bài toán này. Thật ra lúc làm bài tập này, mình cũng nghĩ là mình làm như thế là chưa tối ưu lắm, có điều...tại đang làm project môn CTDL2 nên hơi phân tâm (cộng thêm kidkid hối thúc) nên chẳng nghĩ ra.
@pete: pete mà là gà thì neverland chắc chỉ là gà con.
Đúng là dùng đệ quy hao tổn bộ nhớ rất nặng, theo như mình nghĩ thì chỉ khi nào không thể giải quyết các bài toán bằng các bước đơn giản thì mới nghĩ đến đệ quy. Ý neverland muốn nói là chúng ta nên cân bằng giữa việc dùng đệ quy và không dùng đệ quy.
Hi,pete lại đúng nữa, cần phải xử lý tình huống cho chương trình. Tiếc là trong C không có lệnh nắm bắt tình huống try ...catch như C# nên có vẻ khó khăn cho programmer. Ví dụ, nếu mình chia 1 số cho 0, chắc chương trình của mình bị crash ngay lập tức.
À, nhân nói về việc tràn số, mình đang điên cái đầu về bài tính 100!. Bạn nào có thể giúp mình giải quyết việc tràn số này?

kidkid
13-03-2007, 05:46 PM
Ha ha bài toán 100 giai thừa hả ! Định nghĩa 1 kiểu mới (int) sao đó cấp phát bộ nhớ lại cho nó , hông bit dậy có ổn hông nữa

neverland87
13-03-2007, 05:50 PM
Ha ha bài toán 100 giai thừa hả ! Định nghĩa 1 kiểu mới (int) sao đó cấp phát bộ nhớ lại cho nó , hông bit dậy có ổn hông nữa

Hix, cho kidkid dùng kiểu double luôn á, bảo đảm vẫn bị lỗi tràn. neverland thử dùng kiểu decimal trong C# (có vùng giá trị lớn hơn các kiểu của C/C++) mà nó vẫn bị lỗi tràn. Chẳng lẽ bó tay ở đây ư? Đúng là "có những lúc chuyện nhỏ tưởng như là dễ, mà đụng tay vào mới thấy nó "dễ" cỡ nào".

Xcross87
13-03-2007, 07:20 PM
100! xử lý trong C hơi khó ....*_*...có khi " unsigned char* __32bit MộtTrămGiaiThừa = NULL; "

Có được cái này thì phê quá. Đếm số các chữ số rồi convert về số nguyên cũng sướng.

Còn 1 số chia cho 0 thì làm 1 câu rẽ nhánh là được :
" if ( cái gì đó chia cho 0 ) >>> In ra :" Nhập sai rồi cu, định chơi anh à ! "
Cũng thấy khá giống try ... catch .. throw nhỉ ^_^!

shinichi_haha
13-03-2007, 07:49 PM
Bài này kid kid đố neverland, giải xong òi, có điều chắc là không hay lắm thì phải, thôi thì cứ post code cho mọi người tối ưu giùm mình


#include<stdio.h>
#include<conio.h>
int TongUocSo(int n,int i)
{
if (i==n) return 0;
else if (n%i==0)
{
return i+TongUocSo(n,i+1);
}
else
{
return TongUocSo(n,i+1);
}
}
void main()
{
clrscr();
int n;
printf("n = ");
scanf("%d",&n);
printf("\nTong cac uoc so cua %d la %d",n,TongUocSo(n,1));
getch();
}


Lấy suy nghĩ của cậu shi viết gọn lại như sau:


#include<stdio.h>
#include<conio.h>
int TongUocSo(int n,int i)
{
if (i==n) return 0;
return n%i==0 ? i+TongUocSo(n,i+1):TongUocSo(n,i+1);
}
void main()
{

int n;
printf("n = ");
scanf("%d",&n);
printf("\nTong cac uoc so cua %d la %d",n,TongUocSo(n,1));
getch();
}

kidkid
15-03-2007, 09:00 AM
return n%i==0 ? i+TongUocSo(n,i+1):TongUocSo(n,i+1);

Hay lắm ! a>b? a:b học hoài mà không áp dụng được gì , công nhận shi nhà ta nghĩ ra hay thật !

TQN
17-03-2007, 10:20 PM
Hè hè, nhưng trong lập trình thực tế thì lại không nên dùng kiểu rút gọn a > b ? a : b. Nên viết tường minh như trên, chỉ tốn công gõ code một chút, cộng một ít byte cho file source, nhưng lại dể đọc, dể hiểu, dể bảo trì, không sợ buồn ngủ gõ lộn > thành <, rồi lằng nhằng cái biểu thức phía sau, khó đọc, dài dòng, nếu có bug thì càng mệt, khó sữa. Compiler sinh mã như nhau, chả nhanh hơn hay nhỏ hơn gì đâu.

kidkid
18-03-2007, 04:48 PM
Mình thấy cũng được đấy chứ , vấn đề ở đây chưa hẳn đã là vấn đề liên quan đến code , complier hay ... , kidkid nghĩ rằng việc áp dụng a?b a:b trong bài trên là rất hay , chúng ta đã học được nhiều lệnh như lệnh trên nhưng việc đổi mới cách viết cách suy nghĩ thì ... nói sáng tạo thì cũng hông đúng nhưng nếu kidkid là giáo viên thì sẽ thêm 1 điểm + cho bài của SHI ok ?

neverland87
18-03-2007, 05:01 PM
Mình thấy cũng được đấy chứ , vấn đề ở đây chưa hẳn đã là vấn đề liên quan đến code , complier hay ... , kidkid nghĩ rằng việc áp dụng a?b a:b trong bài trên là rất hay , chúng ta đã học được nhiều lệnh như lệnh trên nhưng việc đổi mới cách viết cách suy nghĩ thì ... nói sáng tạo thì cũng hông đúng nhưng nếu kidkid là giáo viên thì sẽ thêm 1 điểm + cho bài của SHI ok ?

Cộng 1 điểm cho 1 đoạn code tương đồng nhau về hành động thì chẳng đáng cho lắm. Đối với bản thân mình, neverland không thích đoạn code trên vì cùng quan điểm với bạn TQN á. Phần mềm làm ra là để cho người sử dụng (rành và không rành về IT dùng), họ không quan tâm bạn viết code như thế nào, cái họ quan tâm là tính ứng dụng của chương trình, chiếm ít bộ nhớ, chạy nhanh,.. Do đó, nếu là 1 ông thầy dễ tính, neverland sẽ chấm điểm cao cho những bạn nào viết 1 đoạn code mà có thể thay đổi được độ phức tạp của thuật toán (ấy mới chính là viết code sáng tạo)