ݺߣ

ݺߣShare a Scribd company logo

Chuỗi số tăng dần lớn nhất

•
•
ANHMATTROI
ANHMATTROI
1 of 3
Download to read offline
1 Chuỗi số tăng dần lớn nhất - Gọi mảng ban đầu là M[] chứa các phần tử cần tìm chuỗi tăng dần lớn nhất trong mảng - Khởi tạo 2 mảng: rỗng + Mảng chiso[] chứa chỉ số của các số tăng dần lớn nhất trong mảng M + Mảng giatri[] chứa các phần tử của chuỗi tăng dần lớn nhất trong mảng M - Cho chỉ số i chạy từ đầu đến cuối mảng M + Nếu mảng giatri rỗng hoặc M[i] lớn hơn hoặc bằng giá trị cuối cùng của mảng giatri thì thêm: M[i] vào cuối cùng của mảng giatri, thêm chỉ số i vào cuối cùng của mảng chiso. + Ngược lại: nếu M[i] nhỏ hơn phần tử cuối cùng của mảng giatri thì: tìm phần tử nhỏ nhất trong các phần tử lớn hơn hoặc bằng M[i](tìm các phần tử lớn hơn hoặc bằng M[i] trong mảng giatri, sau đó lấy phần tử nhỏ nhất). - Duyệt lại mảng chiso tìm chuỗi tăng dần lớn nhất: + Cho i chạy từ vị trí cuối về đầu tìm những vị trí chỉ số không đúng: mảng chỉ số đúng của dãy tăng đần lớn nhất là giảm dần từ cuối về đầu i = số phần tử của mảng chiso – 1; while(i > 0) { if(chiso[i] < chiso[i-1]) { + Tìm trên mảng M chỉ số của phần tử lớn nhất trong những phần tử nhỏ hơn M[chiso[i]] trong khoảng [i; chiso[i]), thay chiso[i-1] = bằng chỉ số của phần tử tìm được. } i--; } - Ví dụ: tìm chuỗi tăng dần lớn nhất của dãy số sau: 3, 7, 5, 2, 6, 8, 1, 4, 9 i 0 1 2 3 4 5 6 7 8 M 3 7 5 2 6 8 1 4 9
2 i = 0; M[0] = 3; chiso[] = {0}; giatri[] = {3}; i = 1; M[1] = 7; chiso[] = {0, 1}; giatri[] = {3, 7}; i = 2; M[2] = 5; chiso[] = {2, 1}; giatri[] = {5, 7}; i = 3; M[3] = 2; chiso[] = {3, 1}; giatri[] = {2, 7}; i = 4; M[4] = 6; chiso[] = {3, 4}; giatri[] = {2, 6}; i = 5; M[5] = 8; chiso[] = {3, 4, 5}; giatri[] = {2, 6, 8}; i = 6; M[6] = 1; chiso[] = {6, 4, 5}; giatri[] = {1, 6, 8}; i = 7; M[7] = 4; chiso[] = {7, 4, 5}; giatri[] = {4, 6, 8}; i = 8; M[8] = 9; chiso[] = {7, 4, 5, 8}; giatri[] = {4, 6, 8, 9}; + Kết quả bước 1: chiso[] = {7, 4, 5, 8}; giatri[] = {4, 6, 8, 9}; + Duyệt lại mảng chỉ số: trong mảng chỉ số ta thấy 7 không đúng thứ tự giảm dần tại chiso[0]. Từ vị trí chiso[4-1] trong khoảng (0, chiso[4-1]] ở mảng M tìm số lớn nhất trong những số nhỏ hơn M[chiso[4]] ta được số 5 tại chỉ số 2. Thay chỉ số 7 là 2 trong mảng chiso, giá trị 4 là 5 trong mảng giá trị  Chuỗi tăng dần lớn nhất là: 5, 6, 8 , 9 - Code: int* LongestIncrement(int *mang, int n) { if(n < 2) return mang; int chiso[100], i_chiso, i, j; int giatri[100], i_giatri; i_chiso = 0; i_giatri = 0; //khoi tao giatri[i_giatri] = mang[0]; chiso[i_chiso] = 0; for(i = 1; i < n; i++) { if(mang[i] > giatri[i_giatri]) { i_giatri++; giatri[i_giatri] = mang[i]; i_chiso++; chiso[i_chiso] = i; } else { j = i_giatri; while(j > -1) {
3 if(giatri[j] >= mang[i]) j--; else break; } j++; giatri[j] = mang[i]; chiso[j] = i; } } for(i = 0; i <= i_chiso; i++) cout<<chiso[i]<<" "; //duyệt tìm kết quả int *ketqua = new int[100]; int min, tam; i = i_chiso; ketqua[0] = i_chiso + 2; while(i > 0) { if(chiso[i] < chiso[i -1]) { j = chiso[i]; tam = mang[j]; while(j > 0 && tam < mang[j-1]) j--; j--; min = mang[j]; i_chiso = j; while(j > -1) { if(mang[j] < tam && min < mang[j]) { min = mang[j]; i_chiso = j; } j--; } chiso[i-1] = i_chiso; ketqua[i+1] = tam; } else ketqua[i+1] = mang[chiso[i]]; i--; } ketqua[1] = mang[chiso[0]]; return ketqua; }

More Related Content

Chuỗi số tăng dần lớn nhất

  • 1. 1 Chuỗi số tăng dần lớn nhất - Gọi mảng ban đầu là M[] chứa các phần tử cần tìm chuỗi tăng dần lớn nhất trong mảng - Khởi tạo 2 mảng: rỗng + Mảng chiso[] chứa chỉ số của các số tăng dần lớn nhất trong mảng M + Mảng giatri[] chứa các phần tử của chuỗi tăng dần lớn nhất trong mảng M - Cho chỉ số i chạy từ đầu đến cuối mảng M + Nếu mảng giatri rỗng hoặc M[i] lớn hơn hoặc bằng giá trị cuối cùng của mảng giatri thì thêm: M[i] vào cuối cùng của mảng giatri, thêm chỉ số i vào cuối cùng của mảng chiso. + Ngược lại: nếu M[i] nhỏ hơn phần tử cuối cùng của mảng giatri thì: tìm phần tử nhỏ nhất trong các phần tử lớn hơn hoặc bằng M[i](tìm các phần tử lớn hơn hoặc bằng M[i] trong mảng giatri, sau đó lấy phần tử nhỏ nhất). - Duyệt lại mảng chiso tìm chuỗi tăng dần lớn nhất: + Cho i chạy từ vị trí cuối về đầu tìm những vị trí chỉ số không đúng: mảng chỉ số đúng của dãy tăng đần lớn nhất là giảm dần từ cuối về đầu i = số phần tử của mảng chiso – 1; while(i > 0) { if(chiso[i] < chiso[i-1]) { + Tìm trên mảng M chỉ số của phần tử lớn nhất trong những phần tử nhỏ hơn M[chiso[i]] trong khoảng [i; chiso[i]), thay chiso[i-1] = bằng chỉ số của phần tử tìm được. } i--; } - Ví dụ: tìm chuỗi tăng dần lớn nhất của dãy số sau: 3, 7, 5, 2, 6, 8, 1, 4, 9 i 0 1 2 3 4 5 6 7 8 M 3 7 5 2 6 8 1 4 9
  • 2. 2 i = 0; M[0] = 3; chiso[] = {0}; giatri[] = {3}; i = 1; M[1] = 7; chiso[] = {0, 1}; giatri[] = {3, 7}; i = 2; M[2] = 5; chiso[] = {2, 1}; giatri[] = {5, 7}; i = 3; M[3] = 2; chiso[] = {3, 1}; giatri[] = {2, 7}; i = 4; M[4] = 6; chiso[] = {3, 4}; giatri[] = {2, 6}; i = 5; M[5] = 8; chiso[] = {3, 4, 5}; giatri[] = {2, 6, 8}; i = 6; M[6] = 1; chiso[] = {6, 4, 5}; giatri[] = {1, 6, 8}; i = 7; M[7] = 4; chiso[] = {7, 4, 5}; giatri[] = {4, 6, 8}; i = 8; M[8] = 9; chiso[] = {7, 4, 5, 8}; giatri[] = {4, 6, 8, 9}; + Kết quả bước 1: chiso[] = {7, 4, 5, 8}; giatri[] = {4, 6, 8, 9}; + Duyệt lại mảng chỉ số: trong mảng chỉ số ta thấy 7 không đúng thứ tự giảm dần tại chiso[0]. Từ vị trí chiso[4-1] trong khoảng (0, chiso[4-1]] ở mảng M tìm số lớn nhất trong những số nhỏ hơn M[chiso[4]] ta được số 5 tại chỉ số 2. Thay chỉ số 7 là 2 trong mảng chiso, giá trị 4 là 5 trong mảng giá trị  Chuỗi tăng dần lớn nhất là: 5, 6, 8 , 9 - Code: int* LongestIncrement(int *mang, int n) { if(n < 2) return mang; int chiso[100], i_chiso, i, j; int giatri[100], i_giatri; i_chiso = 0; i_giatri = 0; //khoi tao giatri[i_giatri] = mang[0]; chiso[i_chiso] = 0; for(i = 1; i < n; i++) { if(mang[i] > giatri[i_giatri]) { i_giatri++; giatri[i_giatri] = mang[i]; i_chiso++; chiso[i_chiso] = i; } else { j = i_giatri; while(j > -1) {
  • 3. 3 if(giatri[j] >= mang[i]) j--; else break; } j++; giatri[j] = mang[i]; chiso[j] = i; } } for(i = 0; i <= i_chiso; i++) cout<<chiso[i]<<" "; //duyệt tìm kết quả int *ketqua = new int[100]; int min, tam; i = i_chiso; ketqua[0] = i_chiso + 2; while(i > 0) { if(chiso[i] < chiso[i -1]) { j = chiso[i]; tam = mang[j]; while(j > 0 && tam < mang[j-1]) j--; j--; min = mang[j]; i_chiso = j; while(j > -1) { if(mang[j] < tam && min < mang[j]) { min = mang[j]; i_chiso = j; } j--; } chiso[i-1] = i_chiso; ketqua[i+1] = tam; } else ketqua[i+1] = mang[chiso[i]]; i--; } ketqua[1] = mang[chiso[0]]; return ketqua; }