Ừ ! thangtcnb hiểu đúng rồi đó ! Đúng là cách của bạn nguyênthanhhungcntt không sai nhưng lại sai nếu đề bài chính là ví dụ mà comeonbaby đưa ra
Mình dùng TC, Visual 2005 và Dev-cpp. Do mình không có VC6 nên ko debug được. Mà do mình xài class nên nhìn nó rối răm, để mình sữa lại cho đơn giản.
Trả lời luôn cho bạn :
ptr[size] = 10000;//khởi tạo phần tử lính canh
Thực ra chỗ này là gán cho nó 1 giá trị + vô cực thôi ( có thể thêm header file #include<limits> )
sữa thành INT_MAX cũng được. Còn tại sao mình dùng lính canh thì bạn để ý câu lệnh này sẽ hiểu :
PHP Code:
for(int x = position; x < size; x++){
if(ptr[x+1] > ptr[x]){ //Nếu dãy tăng
Lúc x = size nó sẽ so sánh với ptr[size+1], vậy nếu không có phần tử lính canh thì ta phải thêm 1 câu lệnh điều kiện gì đó ( đại khái giải quyết 1 ngoại lệ này, vậy thì mình dùng lính canh để cho đỡ xét thôi )
Cái này là bộ khởi tạo ( gọi là initializer ) ý nói thằng dấu 2 chấm sau constructor á. Nếu khởi tạo cho thành viên có thuộc tính const thì bắt buộc phải dùng nó, nhưng nếu không phải const thì cũng không sao. Mình để vậy cho gọn thôi còn nếu không thì :
PHP Code:
Array::Array()//:size(10)
{
size = 10; ( Để nó ở đây )
ptr = new int[size + 1];
for(int x = 0; x < size; x++){
*(ptr + x) = 0;
}
ptr[size] = 10000;//khởi tạo phần tử lính canh
position = 0;
max_length = 1;
}
Đây mình viết lại không dùng class cho bạn dễ đọc, nếu bạn còn gì thắc mắc mình sẽ giải thích. Thân !
PHP Code:
#include <iostream>
#include <fstream>
#include <limits>//for INT_MAX
using namespace std;
void Read_input_from_user_and_Initialization();
void Search_longest_segment();
void Print_result();
void Reclaim_memory();
int *ptr;
int position,
max_length,
size;
int main()
{
Read_input_from_user_and_Initialization();
Search_longest_segment();
Print_result();
Reclaim_memory();
system("pause");
return 0;
}
void Read_input_from_user_and_Initialization()
{
cout << "Size of array : ";
cin >> size;
ptr = new int[size + 1];
for (int x = 0; x < size; x++){
cout << "The element [" << x << "] :";
cin >> ptr[x];
}
ptr[size] = INT_MAX;//kho+?i ta.o pha^`n tu+? lính canh
position = 0;
max_length = 1;
}
void Print_result()
{
cout << "\nMaximum length of sub-segment : " << max_length - 1 << endl;
cout << "End position : " << position << endl;
for (int x = position - 1; x >= (position - max_length + 1); x--){
cout << "The element [" << x << "] :" << ptr[x] << endl;
}
}
void Search_longest_segment()
{
int count = 1;
for(int x = position; x < size; x++){
if(ptr[x+1] > ptr[x]){ //Ne^'u dãy ta(ng
count++; //ta(ng ?o^. dài
if(count >= max_length){ //ne^'u lo+'n ho+n ?o^. dài tru+o+'c ?ó
max_length = count;
position = x + 1;
}
}
else{//Dãy không ta(ng, ca^.p nha^.t la.i bie^'m ?e^'m
count = 1;
position = x; //Ba('t ?a^`u tu+` vi. trí x
}
}
}
void Reclaim_memory()
{
delete[] ptr;
ptr = NULL;
}
Thuật toán tìm dãy có độ dài lớn nhất
Nguyên bản được gửi bởi comeonbaby
Thuật toán tìm dãy có độ dài lớn nhất
