Nhờ các bạn xem bài này giùm nên làm thế nào

Cho một văn bản gồm N dòng. Các ký tự được lấy từ tập các chữ cái và chữ số.
Yêu cầu: Tìm số lượng ký tự của dòng ngắn nhất, số lượng ký tự của dòng dài nhất và số lượng ký tự của văn bản.
Dữ liệu vào: Cho trong file văn bản CAU3.INP, có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N là số dòng của văn bản (1 ≤ N ≤ 100).
- N dòng tiếp theo: Mỗi dòng ghi một xâu gồm L ký tự (0 < L < 255).
Dữ liệu ra: Ghi ra file văn bản CAU3.OUT, theo cấu trúc như sau:
- Dòng 1: Ghi 3 số nguyên dương x y z. Trong đó: x là số lượng ký tự của dòng ngắn nhất; y là số lượng ký tự của dòng dài nhất, z là số lượng ký tự của văn bản. Các số được ghi cách nhau ít nhất một dấu cách.
Ví dụ:
CAU3.INPCAU3.OUT
3
ThiHSG09
Nam2015
Vong1
5 8 20

BÀI 2
Trong mùa mưa lũ tại các tỉnh miền Trung, có N bạn học sinh cần sang sông để đi học, với phương tiện là một chiếc thuyền tự lái. Chiếc thuyền tự lái này chỉ chở được tối đa là 2 người trên mỗi chuyến đi. Bạn thứ i nếu sang sông một mình sẽ mất thời gian là M. Bạn thứ i và thứ j cùng sang sông sẽ mất thời gian Max(M, M[j]). Em hãy lập trình giúp các bạn đó tính thời gian nhỏ nhất có thể để đưa được tất cả các bạn qua sông cho kịp giờ vào lớp.
Ví dụ:
N=7
M: 2 3 5 6 4 10 14
Thời gian nhỏ nhất cần tìm là: 45
Dữ liệu vào từ file: hsg3.inp
Dòng 1: Số học sinh N
Dòng 2: Thời gian sang sông của từng bạn M, i=1,2,…,N.
Dữ liệu ra file: hsg3.out
Dòng 1: Thời gian nhỏ nhất để đưa tất cả các bạn qua sông.
Ví dụ:
Dữ liệu vào từ file: hsg3.inp
7
2 3 5 6 4 10 14
Dữ liệu ra file: hsg3.inp
45
 

tengiday

Happy life
Bài 1 là kỹ thuật lập trình.

Bài 2:
- Cái chính là bạn cần giữ 2 người có thời gian bé nhất ở 2 bờ để chèo thuyền (đề không nói rõ, nhưng cần có người chèo thuyền trở về).
- Ví dụ:
a) (2, 3) sang sông rồi 2 trở về.
b) (14, 10) sang sông rồi 3 trở về (lấy từ cặp lớn tới nhỏ).
c) (2, 3) sang sông rồi 2 trở về (bước này đảm bảo 2 bờ sông cần có ng` có thời gian bé nhất để chèo thuyền).
d) ......
Bạn làm bằng tay cho hiểu rồi sẽ tự code được nhé.

Good luck.
 
bài 1 : mình muốn hỏi là
với cách như thế mình tính xây dựng một hàm để đếm kí tự.nhưng hàm thì chỉ lấy lại được một kết quả.nên mình ko biết hàm này sẽ đếm như thế nào.chẳng nhẽ phải xây dựng ba hàm.mỗi hàm một công việc.
 

tengiday

Happy life
Bạn không cần xây dựng 3 hàm đâu. Bạn đọc dữ liệu xong là in kết quả ra luôn ấy chứ. Bạn để 3 biến lưu độ dài ngắn nhất, độ dài dài nhất, và tổng ký tự là được. 1 chuỗi đọc vào là xử lý ngay, không cần lưu lại. Bài 1 đơn giản, bạn làm thế nào cũng được.
 
Em theo ví dụ của anh tengiday thì viết như sau. Em k biết Pascal, nhưng em nghĩ nó cũng khá giống C.
[ah]
Mã:
void qsort(int *a, int L, int R) {
    if (L < R) {
        int i = L, j = R, mid = a[i+(j-i)/2];
        while (i < j) {
            while (a[i] > mid) i++;
            while (a[j] < mid) j--;
            if (i <= j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
                i++;
                j--;
            }
        }
        qsort(a, L, j);
        qsort(a, i, R);
    }
}

int river_crossing(int *a, int n) {
    if (n < 1)
        return 0;
    if (n < 2)
        return a[0];
    
    qsort(a, 0, n-1); // sap xep tu lon toi nho
    
    int tg = a[n-2], // Cap co thoi gian nho nhat sang song. Day la buoc khoi dong bat buoc.
        i;
    for (i = 0; i < n-2; i += 2) {
        tg += a[n-1] + a[i]; // Con nguoi o bo song, nen nguoi nho nhat a[n-1] phai tro ve. Sau do a[i] qua song.
        
        // Neu so luong nguoi la le thi a[i] sang song se dan theo a[n-1]. Day la chuyen cuoi cung.
        // Neu so luong nguoi la chan thi a[i] sang song se dan theo a[i+1]. Sau do a[n-2] phai quay ve de don a[n-1] sang song.
        if (i < n-3)
            tg += a[n-2] + a[n-2];
    }
    
    return tg;
}
[/ah]
Quy tắc như anh kia đã nói vậy. Nếu từ bờ A xuất phát qua bờ B thì:
1) Sắp xếp dãy a giảm dần.
2) Cho hai người cuối danh sách sang sông (a[n-1] và a[n-2]) qua bờ B.
Nếu vẫn còn người ở bờ sông bên A thì thực hiện như sau:
3) Cho người có thời gian nhỏ hơn (tức là a[n-1]) từ B trở về bờ A.
4) Cho 2 người có thời gian lớn nhất từ A sang B.
Lưu ý nếu số người là lẻ thì đây là đợt cuối. Nếu k thì thực hiện bước sau:
5) Cho a[n-2] từ B quay về A. Đây là người có thời gian qua sông thấp thứ 2.
Lúc này a[n-1] và a[n-2] đã ở bờ A.
6) Quay lại bước 2.
 
Bài 2: mình suy nghĩ code mãi mà không ra.nhờ bạn giải giúp được không ạ
Bài này chỉ cần đệ quy là ra mà.
Yêu cầu rõ ràng là thời gian sang. Bỏ qua thời gian thuyền về vì nó là tự lái và thời gian quay về không đề cập.

Dữ liệu đầu vào theo ví dụ sẽ phân tích như sau:

N=7
M: 2 3 5 6 4 10 14
Thời gian nhỏ nhất cần tìm là: 45

Tổng số người cần thực hiện là 7. Theo đề bài mỗi lần có thể chở được 2 người. Vậy tổng số cặpp sẽ phải là 7/2+1 = 4(lấy phần nguyên).

Bây giờ nhiệm vụ của bạn còn lại là: Tạo một vòng lặp để tính toán lấy ra thời gian nhỏ nhất với 4 cặp số trong dãy M nữa là xong.
Bạn thự hiện đệ quy để lấy kết quả.

Giải thuật đã có, giờ chỉ còn nhiệm vụ thực hiện nữa là xong.
 
Bài 1 là kỹ thuật lập trình.

Bài 2:
- Cái chính là bạn cần giữ 2 người có thời gian bé nhất ở 2 bờ để chèo thuyền (đề không nói rõ, nhưng cần có người chèo thuyền trở về).
- Ví dụ:
a) (2, 3) sang sông rồi 2 trở về.
b) (14, 10) sang sông rồi 3 trở về (lấy từ cặp lớn tới nhỏ).
c) (2, 3) sang sông rồi 2 trở về (bước này đảm bảo 2 bờ sông cần có ng` có thời gian bé nhất để chèo thuyền).
d) ......
Bạn làm bằng tay cho hiểu rồi sẽ tự code được nhé.

Good luck.
Đây là thuyền tự lái nên bác không cần giữ 1 người quay về. Theo đề bài đã đưa ra mà. Chúng ta khi làm sẽ căn cứ theo đề bài chứ không đưa thêm tham số vào.
 
Nhưng mà kết quả theo dữ liệu đầu vào
N=7
M: 2 3 5 6 4 10 14
Thời gian nhỏ nhất cần tìm là: 45 => 45 là không đúng.
Tại sao không đúng: Dãy M có tổng là: 44. Trong khi mỗi lần sang tối đa đã được 2 người. Thì nghĩa là tổng thời gian lớn nhất cũng chỉ 44 nếu đi từng người. Không bao giờ lên được 45.

Kết quả bài này khi chạy phải là: 14+6+4+2 = 26.

Mục đích bài này đơn giản là chuyển cái mảng M thành cặp (a;b) có tổng 2 số lớn nhất trong mảng chưa được chọn.

Khi chạy trên giấy sẽ thực hiện các bước như sau:

Vòng 1 1: Hỏi trong mảng 2 số lớn nhất trong mảng M. Kết quả là 14 và 10. Lấy ra số lớn nhất trong 2 số: Bạn được 14. Loại 14, 10 ra khỏi mảng M.
Vòng 2: Hỏi trong mảng 2 số lớn nhất tỏng mảng M thu được từ bước 1. Kết quả laf6 và 5. Lấy 2 số lớn nhất trong 2 số bạn được 6. Loại 5, 6 ra khỏi mảng M.
Vòng 3: Tương tự lấy được 3, 4 => lấy ra 4.
Vòng 4: Chỉ còn 1 số 2, nên sẽ lấy ra số 2.

Tổng 4 vòng kết quả là 14+6+4+2 = 26.

Bạn đưa vào đệ quy như sau:

function tongmin(n,m,total){
/*
n là số người cần chuyển sang
m là mảng thời gian của mỗi người. Sau này có thể loại bỏ tham số n vì trong m đã có thông tin này rồi
total là tổng thu được sau mỗi lần lặp, bạn phải truyền vào đệ quy để không cần tạo thêm biến khác.
*/
//Lấy ra 2 số lớn nhất trong mảng m => kỹ thuật lập trình
//Loại bỏ 2 phần tử vừa lấy ra khỏi mảng m, nhớ giảm n = n-2;(Mỗi lượt chở được 2 người)
//nếu n <=0 thì in ra màn hình total và thoát đệ quy, ngược lại thì gọi hàm
//total=total+số lớn nhất trong 2 số vừa thu được.
tongmin(n,m,total);

}


 
Nói đơn giản đề bài 2 không hợp lý thì khỏi cần giải

Để dễ hình dung: bài toán là người lái đò chở học sinh qua sông, người lái đò chịu trách nhiệm cầm lái, trên thuyền có 2 chỗ trống chở học sinh và chỉ có duy nhất 1 thuyền chở học sinh sang sông

Chở 1 học sinh mất M
Chở 2 học sinh mất MAX(M, M[j])
Không chở học sinh mất ???

Thuyền từ bên bờ A sang bờ B thì phải quay lại đón lượt học sinh kế tiếp, lúc đó thuyền không chở học sinh nào cả

Nói đơn giản bài này muốn thỏa mã MIN thỏa mãn 2 điều kiện

- mỗi lần chở phải đạt tối đa 2 học sinh nếu có thể
- mỗi lần chở phải có 2 học sinh có thời gian lâu nhất

Học PASCAL (hoặc các ngôn ngữ khác) nên tải cuốn Giải thuật và lập trình của LÊ MINH HOÀNG về xem, khá là bổ ích
 
Ối em xem thấy có bài cũng bảo chủ thớt đề sai. Sau đó chủ thớt nói lại cho vỡ mồm mà vẫn k biết. Đề đúng hay sai là do bạn thớt định nhé mọi người.Còn cách làm của bạn rchato thì k tối ưu chút nào. Hiểu theo kiểu của bạn mà làm thế thì k hay rồi. Cần phải sắp xếp lại trước sẽ nhanh hơn. Bạn k tin thì viết code ra sẽ test. Có cái code mà test thì "anh chỉ biết câm nín".
 
Ối em xem thấy có bài cũng bảo chủ thớt đề sai. Sau đó chủ thớt nói lại cho vỡ mồm mà vẫn k biết. Đề đúng hay sai là do bạn thớt định nhé mọi người.Còn cách làm của bạn rchato thì k tối ưu chút nào. Hiểu theo kiểu của bạn mà làm thế thì k hay rồi. Cần phải sắp xếp lại trước sẽ nhanh hơn. Bạn k tin thì viết code ra sẽ test. Có cái code mà test thì "anh chỉ biết câm nín".

Trong lập trình thì điều đầu tiên cần làm được là phải chạy được. Còn tối ưu là khi đã hiểu rồi, đã cho chạy được rồi mới nói tới tối ưu. Mình cũng là dân lập trình. Có thể tìm theo thông tin thanhhait92 để biết thêm thông tin.

Mình phân tích, đưa ra các bước như vậy mục đích là để chủ thớt hiểu vấn đề, hiểu giải thuật. Vì chủ thớt chưa hiểu được bài toán để chạy thì nói gì tới chuyện tối ưu. Bao giờ nắm vững giải thuật, chạy được thực tế trên giấy, trên máy thì lúc đó mới nói tới tối ưu hóa câu lệnh.
Giống như học chữ vậy, phải học từng chữ cái rồi lúc đó mới học ghép chữ, rồi mới học làm văn. Viết chữ còn chưa biết thì làm sao biết làm văn hay.
 
Ối em xem thấy có bài cũng bảo chủ thớt đề sai. Sau đó chủ thớt nói lại cho vỡ mồm mà vẫn k biết. Đề đúng hay sai là do bạn thớt định nhé mọi người.Còn cách làm của bạn rchato thì k tối ưu chút nào. Hiểu theo kiểu của bạn mà làm thế thì k hay rồi. Cần phải sắp xếp lại trước sẽ nhanh hơn. Bạn k tin thì viết code ra sẽ test. Có cái code mà test thì "anh chỉ biết câm nín".
Chẳng có gì là đề đúng hay sai do thớt định nghĩa, sách giáo khoa nhà xuất bản giáo dục còn đầy chỗ không đúng, nói thẳng là sai lù lù, các thầy cô giáo dạy lâu năm phát hiện ra mà sách vẫn không chịu sửa nha bạn, học miết thành quen, ấn bản lần thứ A, B, C tái bản lại mà không chịu sửa các lỗi trong bản trước, sách giải thuật lập trình cũng vậy thui, đọc nhiều thì biết

chủ yếu đề bài đặt vấn đề không cụ thể, dễ gây hiểu lầm, cần ít nhất 1 người trên thuyền nhấn nút khởi động, thay vì nói thuyền tự lái, cách giải của tengiday mình chưa chứng minh được tổng thời gian sẽ luôn MIN, chỉ chứng minh được nó ra kết quả giống ví dụ

MAX(2, 3) => 2 (Time: 5)
MAX(10, 14) => 3 (Time: 17)
MAX(2, 3) => 2 (Time: 5)
MAX(5, 6) => 3 (Time: 9)
MAX(2, 3) => 2 (Time: 5)
MAX(3, 4) => (Time: 4)

Time: 5 + 17 + 5 + 9 + 5 + 4 = 45
 
Chẳng có gì là đề đúng hay sai do thớt định nghĩa, sách giáo khoa nhà xuất bản giáo dục còn đầy chỗ không đúng, nói thẳng là sai lù lù, các thầy cô giáo dạy lâu năm phát hiện ra mà sách vẫn không chịu sửa nha bạn, học miết thành quen, ấn bản lần thứ A, B, C tái bản lại mà không chịu sửa các lỗi trong bản trước, sách giải thuật lập trình cũng vậy thui, đọc nhiều thì biết

chủ yếu đề bài đặt vấn đề không cụ thể, dễ gây hiểu lầm, cần ít nhất 1 người trên thuyền nhấn nút khởi động, thay vì nói thuyền tự lái, cách giải của tengiday mình chưa chứng minh được tổng thời gian sẽ luôn MIN, chỉ chứng minh được nó ra kết quả giống ví dụ

MAX (2, 3) => 2 (Time: 5)
MAX (10, 14) => 3 (Time: 17)
MAX (2, 3) => 2 (Time: 5)
MAX (5, 6) => 3 (Time: 9)
MAX (2, 3) => 2 (Time: 5)
MAX (3, 4) => (Time: 4)

Time: 5 + 17 + 5 + 9 + 5 + 4 = 45

Tùy vào chủ thớt, những cái khác k quan trọng. Bạn muốn hiểu sao thì tùy. Câu trả lời tại sao cách anh tengiday đúng đã nằm ngay trong cách giải của em và rchato rồi. Bạn k thấy được sao???

@rchato: Em thấy trên dd người ta nói đúng thì nghe thôi. Nếu cần uy tín thì nếu bạn biết tengiday là ai, thành tựu của ảnh như thế nào thì bạn có dám bảo anh đó hiểu sai đề k? :troll2:

AHBP nhiều thật. Nói mãi...
 
Sửa lần cuối:
Một bài toán không chỉ cần đưa ra bài giải, mà phải biết vì sao nó đúng? Một người lập trình luôn phải đặt câu hỏi đó? Vì đây là bài toán hoán vị các lần di chuyển nên cần phải chứng minh được vì sao tổng theo cách chọn đó sẽ MIN, để đảm bảo tính đúng đắn của thuật toán. Chỗ nào không hiểu thì mình nói không hiểu?
 
Ý của em là nếu quan sát kĩ sẽ thấy cách làm của anh tengiday = cách làm của bạn rchato + sự di chuyển của cặp có thời gian nhỏ nhất tại mỗi bước. Có đúng k? Còn tại sao chọn như bạn rchato thì em nghĩ nên để bạn ý trả lời cho.
 

Sút toàn trật

Ngoan nhất nhà
Ý của em là nếu quan sát kĩ sẽ thấy cách làm của anh tengiday = cách làm của bạn rchato + sự di chuyển của cặp có thời gian nhỏ nhất tại mỗi bước. Có đúng k? Còn tại sao chọn như bạn rchato thì em nghĩ nên để bạn ý trả lời cho.
Mình đã nói với bạn rồi, không tranh luận làm gì nữa vì họ không bao giờ sai, bạn có thấy ai khen 1 người bảo thủ không, trừ khi người đó mù quán, cái chính cần giải quyết vấn đề, không phải tranh luận vấn đề vậy nên những gì tranh luận vô nghĩa thì mình nên im lặng, không nên chia sẻ, nên chia sẻ đúng người, đúng đối tượng
 
Các bạn kiểm tra lại xem mình có tính sai ở đâu không (tính mình tính toán hay nhầm lẫn, các bạn phải kiểm tra lại cho chắc ăn)

Với bộ số liệu


7
2 10 12 14 16 18 20

Cách 1: Theo cách sắp xếp tengiday

Mã:
Lần 1:  2 10 =>  2 (12) => [10]
Lần 2: 20 18 => 10 (30) => [20 18]
Lần 3:  2 10 =>  2 (12) => [20 18 10]
Lần 4: 16 14 => 10 (26) => [20 18 16 14]
Lần 5:  2 10 =>  2 (12) => [20 18 16 14 10]
Lần 6:  2 12 =>    (12) => [20 18 16 14 10 2 12]
Hoặc
Lần 5:  2 12 =>  2 (14) => [20 18 16 14 12]
Lần 6:  2 10 =>    (10) => [20 18 16 14 12 2 10]

Tổng thời gian: 12 + 30 + 12 + 26 + [12 + 12 hoặc 14 + 10] = 104

Cách 2: Cách sắp xếp khác cho thời gian ngắn hơn bộ số liệu này (thuật toán này không phải chính xác để xử lý bài này, vì chưa nghĩ ra hướng cho thuật toán giải bài này luôn đúng)

Mã:
Lần 1: 2 20 => 2 (22) => [20]
Lần 2: 2 18 => 2 (20) => [20 18]
Lần 3: 2 16 => 2 (18) => [20 18 16]
Lần 4: 2 14 => 2 (16) => [20 18 16 14]
Lần 5: 2 12 => 2 (14) => [20 18 16 14 12]
Lần 6: 2 10 =>   (10) => [20 18 16 14 12 10 2]

Tổng thời gian: 22 + 20 + 18 + 16 + 14 + 10 = 100

So sánh: cách 2 có thời gian ngắn hơn cách 1, suy ra thuật toán tengiday không phải luôn đúng, hay nói đúng hơn là thuật toán giải bài này không chính xác
 
Tùy vào chủ thớt, những cái khác k quan trọng. Bạn muốn hiểu sao thì tùy. Câu trả lời tại sao cách anh tengiday đúng đã nằm ngay trong cách giải của em và rchato rồi. Bạn k thấy được sao???

@rchato: Em thấy trên dd người ta nói đúng thì nghe thôi. Nếu cần uy tín thì nếu bạn biết tengiday là ai, thành tựu của ảnh như thế nào thì bạn có dám bảo anh đó hiểu sai đề k? :troll2:

AHBP nhiều thật. Nói mãi...
Mình đâu nói bạn tengiday làm sai. Mình chỉ nói bạn ấy là không nên đưa dự liệu không có trong bài vào như thế. Vì khi đã đưa như thế thì sẽ có rất nhiều cái phải đưa vào ví dụ như: Lực cản, tốc độ dòng chạy,...
Còn về uy tín và thành tựu. Xin lỗi bạn, mình chỉ cần bài toán được giải quyết xong. Còn lại người nào uy tín mà nói sai thì vẫn phải góp ý. Bạn có thể gọi ban @tengiday vào để bạn ấy trả lời. Chứ mình không nói bạn ấy giải bài toán sai nhé.
 
Em nghĩ em hiểu sai ý anh tengiday rồi. Thêm ví dụ của bạn gunshot9x làm em cũng nghĩ ra phương pháp.
Em giả sử n > 1 cho dễ.
Mã:
1) Sort mảng giảm dần a[1] >= a[2] >= ... >= a[n-1] >= a[n]
2) Với i chạy từ 1 và mỗi bước tăng 2, nếu m là số người còn bên bờ sông A tại mỗi bước thì ta có các trường hợp sau:
   a) Nếu m=3 thì thời gian là a[n] + a[n-1] + a[n-2]
   b) Nếu m=2 thì thời gian là a[n-1]
   c) Nếu m>3 thì có 2 trường hợp:
      c_i)  Nếu a[n-1] và a[n] hộ tống a[i] và a[i+1] qua sông rồi a[n] và a[n-1] quay về,
         khi đó thời gian là: a[n] + 2*a[n-1] + a[i].
      c_ii) Nếu a[n] hộ tống a[i] và a[i+1] qua sông rồi a[n] quay về,
         khi đó thời gian là: 2*a[n] + a[i] + a[i+1].
      Ta chỉ cần chọn số nhỏ hơn của 2 trường hợp c_i và c_ii
Ý tưởng là lúc nào cũng phải để cặp có thời gian qua sông lớn nhất đi trước. Còn "người hộ tống" thì cần giữ 2 đầu. Tại sao nó đúng thì ý nghĩ cũng tương tự là kết hợp người chèo thuyền về và cách chọn cặp lớn tới nhỏ.
Em nói được là làm được. Đây là code. Khuya rồi, em code nhanh rồi ngủ, kiểu này mai chắc ngủ lớp Marx quá.
[ah]
Mã:
int river_crossing(int *a, int n) {
    if (n < 1)
        return 0;
    if (n < 2)
        return a[0];

    qsort(a, 0, n - 1); // sap xep tu lon toi nho

    int tg = 0, i;
    for (i = 0; i < n - 3; i += 2)
        tg += min(a[n - 1] + 2 * a[n - 2] + a[i], 2 * a[n - 1] + a[i] + a[i + 1]);
    return tg + (i < n - 2 ? a[n - 3] + a[n - 2] + a[n - 1] : a[n - 2]);
}
[/ah]
@rchato: Bạn đừng điêu và lươn lẹo nhé!!! Ở đây k phải ở ngoài đời mà bạn dùng kiểu nói làm ăn đó. Tôi không nói anh đi sai luật, tôi bảo anh vượt đèn đỏ. K ai khờ đâu; lòng Tư Mã Chiêu ai cũng hiểu. Như thế em biết công ty thế nào rồi đấy!
 
Top