Duyệt mảng lần 1 từ trái sang phải sắp xếp số lẻ xuống cuối mảng, các số còn lại lên đầu mảng.
Duyệt mảng lần 2 từ phải qua trái sắp xếp đổi chổ các số chẳn đầu tiên và các số 0.
Chào tất cả các bạn! Sory vì đã làm phiền các bạn vào dịp hè này nha
Đây là bài mình đã thắc mắc và suy nghĩ rất lâu. Mà ko thể có được cách giải đúng. Theo các bạn : Các bạn giải thế nào, mình mong sự góp ý từ các bạn nhiều.
Đề : Nhập n phần tử cho mảng. Xuất mảng sao cho Số chẵn nằm trước, số 0 nằm giữa (nếu có), số lẻ nằm phía sau
Sự góp ý của các bạn là bước đầu cho mình hình thành code. Cám ơn rất nhiều
Duyệt mảng lần 1 từ trái sang phải sắp xếp số lẻ xuống cuối mảng, các số còn lại lên đầu mảng.
Duyệt mảng lần 2 từ phải qua trái sắp xếp đổi chổ các số chẳn đầu tiên và các số 0.
/* The thing that I think is the thing that I do. */
Trước tiên, cám ơn bạn đã góp ý cho mình.
bạn có thể chi tiết hơn, việc "sắp xếp số lẻ xuống cuối mảng, số còn lại lên đầu" ko ?
Còn việc thứ 2, nếu trường hợp ko có số 0 nào. Sao mà đổi ?
Trước mình làm một lần rồi nhưng chẳng biết quẳng đi đâu rồi, nay mình làm lại một code demo cho ban:
Code://Chuyen so chan (khac 0) len dau, khong o giua le o cuoi. #include <stdio.h> void chuyen(int a[],int n); int main() { int n=9,a[9]={1,0,3,3,4,2,5,0,7}; int i; chuyen(a,n); for (i=0;i<n;i++) printf("%4d",a[i]); } void chuyen(int a[],int n) { int i,t1=0,t2=n-1; for (i=t1;i<t2;i++) //su ly chan le { while (a[t1]%2==0)t1++; while (a[t2]%2==1)t2--; if (a[i]%2==1) { int b=a[i]; a[i]=a[t2]; a[t2]=b; t2--; } } t2=t1+1;t1=0; for (i=t1;i<t2;i++) //su ly chan va so 0 { while (a[t1]!=0)t1++; while (a[t2]==0)t2--; if (a[i]==0) { int b=a[i]; a[i]=a[t2]; a[t2]=b; t2--; } } }
Tất cả tóm gọn trong hàm này:
C Code:
void sapxep(int a[], int N) { int i, j, t; /* sap xep so le xuong cuoi mang */ for (i = 0; i < N - 1; i++) { for (j = i + 1; j < N; j++) if (a[i] % 2 != 0 && a[j] % 2 == 0) { t = a[i]; a[i] = a[j]; a[j] = t; break; } } /* sap xep doi cho so 0 ra giua so chan va le */ for (i = N - 1; i > 0; i--) { for (j = i - 1; j > -1; j--) if (a[i] % 2 == 0 && a[j] == 0) { t = a[i]; a[i] = a[j]; a[j] = t; break; } } }
Đã được chỉnh sửa lần cuối bởi Chautieu47 : 31-07-2008 lúc 07:58 PM.
/* The thing that I think is the thing that I do. */
Theo mình nghĩ ko nên tách biệt sắp sếp số lẻ và số chẳn thành 2 đoạn mà làm chung.
Hướng giải thế này:
b1: khai báo các biến n,i=0,j=n //n:số phần tử thực sự của mảng
b2: while(i<j){
b3: for(i=0;i<=n;i++) if(a[i] chẳn) break;
b4: for(j=n;j>=0;j--) if(a[j] lẻ) { hoán đổi a[i] và a[j]; break;}
b5: i++; j--;
}
sau khi hoán đổi xong lúc này nếu có số 0 thì nó được tính là chẳn và i là phẩn tử cuối chẳn j là phần tử đầu của phần lẻ .
b6: for(int k=0;k<=i;k++)
b7: if(a[k]==0) {hoán đổi a[k] và a[i]; i--;}
vậy là xong.
có gì thắc mắc bạn cho ý kiến.
Mình chưa kiển tra lại nhưng hi vọng là đúng. Mong nhận lại hồi âm .
Bạn chưa đọc kỹ bài của tui rồi. Vòng for đầu tiên tui sắp xếp số lẻ xuống cuối mảng, các số còn lại bao gồm số chẵn và các số 0 (nếu có) lên đầu mảng. Như vậy ở vòng for này các số chẵn và số lẻ đã được dồn lên đầu và cuối mảng cùng lúc rồi.
Ở vòng for thứ 2 là để đổi chổ các số chẵn đầu tiên (tính từ phải qua trái) với các số 0 (nếu có). Trường hợp không có số 0 nào thì không đổi chổ thôi.
À ở đây tui làm dựa theo giải thuật sắp xếp tăng giảm. Để giảm bớt các phép tính nên để lệnh break; sau mổi lần đổi chổ, cái này là thiết sót của tui đã sửa lại trên kia rồi.
/* The thing that I think is the thing that I do. */
Tại sao cứ phải cứng nhắc làm trên 1 mảng, sao ko dùng 1 mảng phụ?
Tổng hợp nè![]()
C++ Code:
/* http://forums.congdongcviet.com/showthread.php?t=8789 */ #include <iostream> #include <cstdlib> using namespace std; ////////////////////////////////////////////////////////////////////////////////////// const int MAX_N = 10000; int N, A[MAX_N]; /////////////////////////////////////////// void ReadData(){ for (int i=1; i<=N; i++){ } } /////////////////////////////////////////// template<class T> void Swap(T& x, T& y){ T z; z = x; x = y; y = z; } /////////////////////////////////////////// int Order(int x){ if (x%2 == 1) return 1; if (x == 0) return 0; return -1; } /////////////////////////////////////////// // Sort -bruteforce :D void Solution_1(){ for (int i = 1; i<N; i++) for (int j = i+1; j<=N; j++) if (Order(A[i]) < Order(A[j])) Swap(A[i], A[j]); } /////////////////////////////////////////// // Dual array =)) void Solution_2(){ int* B = new int[N]; memcpy(B, A+1, N*sizeof(int)); int l = 1, r =N; for (int i = 0; i<N; i++) if (Order(B[i]) < 0) A[l++] = B[i]; else if (Order(B[i]) > 0) A[r--] = B[i]; if (l<=r) memset(A+l, 0, (r-l+1)*sizeof(int)); delete[] B; } /////////////////////////////////////////// void Solution_3(){ int l = 1, r = N; A[0] = 0; A[N+1] = 1; do{ while (A[l]%2 == 0) l++; while (A[r]%2 != 0) r--; if (l<r) Swap(A[l++], A[r--]); }while(l<r); l = 1; A[0] = 1; A[N+1] = 0; while (l<r){ while (A[l] != 0) l++; while (A[r] == 0) r--; if (l<r) Swap(A[l++], A[r--]); } } /////////////////////////////////////////// void WriteData(){ for (int i = 1; i<=N; i++) } ////////////////////////////////////////////////////////////////////////////////////// int main(){ ReadData(); Solution_1(); WriteData(); system("pause"); return EXIT_SUCCESS; } //////////////////////////////////////////////////////////////////////////////////////
oh! xin cám ơn bài viết của bác!
Sorry vì đã để topic này khá lâu, do em bận tí việc.
Em xin post code của mình lên, cộng thêm vấn đề in ra số nguyên tố nhỏ hơn x
C++ Code:
#include <math.h> #include <conio.h> #include <iostream.h> void Nhap(int a[], int &n) { for(int i=1;i<=n;i++) { } } void Xuat(int a[], int n) { for(int i=1;i<=n;i++) { } } void Sort(int a[], int n) { int b,c,d,e,t,t2; for(b=0;b<=n-1;b++) { for(c=b+1;c<=n;c++) { if ((a[b]%2!=0) && (a[c]%2==0)) { t=a[b]; a[b]=a[c]; a[c]=t; } } } for (d=n-1;d>=1;d--) { for(e=d-1;e>=0;e--) { if ((a[d]%2==0) && (a[e]==0)) { t2=a[e]; a[e]=a[d]; a[d]=t2; } } } } int Ktra_NT(int a) { int kq=1; if(a==2||a==3) return 1; else { if (a==0) return 0; else { for(int i=2;i<=sqrt(a);i++) { if (a%i==0) return 0; } } } return 1; } void main() { int a[100],n,x;char c; do { //clrscr(); Nhap(a,n); Sort(a,n); Xuat(a,n); for(int i=0;i<=n-1;i++) { if ( (a[i]<x) && Ktra_NT(a[i])==1) { } } }while(c=='c'||c=='C'); }
Tuy nhiên, em cũng xin cám ơn lời góp ý của bác huy_nguyen, em sẽ nghiên cứu vấn đề dùng mảng phụ (đây là 1 phương pháp hữu dụng ), em sẽ cố gắng hoàn thành sớm post lên cho mọi người.
Một lần nữa, xin cám ơn mọi người.