Một số bài hướng dẫn về Mảng!

Để xây dựng diễn đàn với các bài hướng dẫn ban đầu cụ thể, tôi xin đưa một số các nội dung hướng dẫn dưới đây!

Ý tưởng chủ yếu của thuật toán này là “chia để trị”. Từ một dãy a ban đầu có n phần tử, ta chọn phần tử mid=a[(n-1)/2] ở chính giữa dãy. Phần tử này dùng để chia dãy đã cho thành 2 dãy con: dãy bên trái chỉ gồm những phần tử không vượt quá mid, dãy con bên phải chỉ gồm những phần tử không nhỏ hơn mid. Sau đó tiếp tục gọi đệ quy với 2 dãy con đó cho đến khi không thể chia thành 2 dãy nhỏ hơn thì dừng. Cuối cùng, ta có dãy đã sắp thứ
tự.
Để biểu diễn thuật toán, dùng thủ tục sap(int *a,int d,int c), thủ tục này sẽ sắp lại dãy a tăng dần từ vị trí d đến c. Trong chương trình chính, thủ tục này sẽ được khởi động bởi lệnh sap(a,0,n-1)
Thuật toán cho thủ tục sap(*a,d,c):
- Dùng 2 biến l và r dùng làm biến chạy từ 2 đầu để đảo giá trị các phần tử của a nếu cần. Khởi tạo l=d,r=c
- Dùng biến mid=a[(d+c)/2] là phần tử ở giữa của dãy
- Thực hiện vòng lặp do:
+ Thực hiện vòng lặp while: Trong khi a[d] tăng d (1)
+ Thực hiện vòng lặp while: Trong khi a[r]>mid thì giảm r
+ Nếu d<=r tức là có 2 phần tử nghịch thế a[d]>a[r] thì đảo giá trị 2 phần tử đó (nếu d=r thì việc đảo không có tác dụng gì), sau đó tăng d, giảm r và quay lại (1) + Vòng lặp do thực hiện cho đến khi d>r. Tức là đã phân thành 2 dãy con đã nêu trên
- Gọi đệ quy: áp dụng thủ tục này cho 2 dãy con từ d đến r (nếu d đến c (nếu r Ví dụ: để sắp dãy a có 10 phần tử: 6, 7, 5, 1, 4, 3, 2, 6, 3, 8, ta làm như sau:
Gọi sap(a,0,n-1)
l=0 ;r=9 ;mid=a[(0+9)/2]=a[4]=4
Thực hiện vòng lặp do :
Sau 2 vòng while, l=0, r=8, đảo giá trị, ta có dãy: 3, 7, 5, 1, 4, 3, 2, 6, 6, 8
Tăng l. giảm r
Tiếp tục quay lại thực hiện 2 vòng while, l=1, r=6, đảo giá trị: 3, 2, 5, 1, 4, 3, 7, 6, 6, 8
Tăng l. giảm r
Tiếp tục quay lại thực hiện 2 vòng while, l=2, r=5, đảo giá trị: 3, 2,
3, 1, 4, 5, 7, 6, 6, 8
Tăng l. giảm r
Tiếp tục quay lại thực hiện 2 vòng while, l=5, r=3. Do l>r nên vòng lặp do kết thúc và dãy a trở thành:
3, 2, 3, 1, 4, 5, 7, 6, 6, 8
Như vậy, các phần tử bên trái mid đều không vượt quá mid, phần tử bên phải đều không nhỏ hơn mid
Do d=0 đến c
Tương tự, sau khi gọi sap(a,0,3), ta có dãy a: 1, 2, 3, 3, 4, 5, 7, 6, 6, 8
Và sap(a,5,9): 1, 2, 3, 3, 4, 5, 6, 6, 7, 8
Dãy a đã được sắp thứ tự. (máy cũng có thể tiếp tục gọi các thủ tục đệ quy nhưng sẽ không ảnh hưởng đến giá trị các phần tử)
Nhận xét: Thuật toán này tuy cài đặt phức tạp hơn nhưng sẽ chạy nhanh hơn vì máy chỉ thực hiện trung bình khoảng nlog2n phép so sánh.

Và đây là chương trình con:

Code:

 void sort(int *a,int d, int c)
 {
      int l,r,mid,tam;
      l=d;r=c;mid=a[(d+c)/2];
      do
      {
          while(a[l]
          while(a[r]>mid)r--;
          if(l<=r)
          {
                tam=a[l];
                a[l]=a[r];
                a[r]=tam;
                l++;r--;
          }
      }
      while(l<=r);
      if(d
      if(l
 }

Xét trường hợp đặc biệt của dãy a: là các số nguyên trong đoạn từ 0 đến M với M không quá lớn.
Trong trường hợp này, ta có một thuật toán đơn giản như sau:
- Xây dựng dãy c[0], c[1], …, c[M] có ý nghĩa: c[i] là số lần xuất hiện của giá trị i trong dãy a
- Khởi tạo c[i]=0 (với mọi i)
- Duyệt dãy a từ 0 đến n, với mỗi phần tử a[i], ta tăng số lần xuất hiện giá trị a[i] lên 1, tức là c[a[i]]++, cập nhật lại M tương tự như tìm số lớn nhất trong dãy a
Ví dụ: sắp xếp dãy a có 12 phần tử như sau: 1,2,2,6,8,8,0,0,1,1,3,3
Sau khi duyệt dãy a, ta có dãy c như sau: c[0]=2, c[1]=3, c[2]=2, c[3]=3, c[4]=c[5]=c[7]=0, c[6]=1, c[8]=2
Xuất từ mảng c, ta được dãy 0,0,1,1,1,2,2,3,3,6,8,8
TỔNG QUÁT : sau khi sắp xếp :
Giá trị 0 đứng trong dãy a từ vị trí 0 đến vị trí c[0]-1
Giá trị 1 đứng trong dãy a từ vị trí c[0] đến vị trí c[0]+c[1]-1
Giá trị 2 đứng trong dãy a từ vị trí c[0]+c[1] đến vị trí c[0]+c[1]+c[2]-1
Giá trị 3 đứng trong dãy a từ vị trí c[0]+c[1]+c[2] đến vị trí c[0]+c[1]+c[2]+c[3]-1
…
Giá trị v đứng trong dãy a từ vị trí c[0]+c[1]+…+c[v-1] đến vị trí c[0]+c[1]+…+c[v-1]+c[v]-1
…
Để ý: sau khi sắp xếp, nếu ta tính lại dãy c như sau: c[i]+=c[i-1] (với mọi i từ 0 đến M) thì c[i]-1 chính là vị trí cuối của đoạn chứa giá trị i trong dãy a sau khi sắp xếp
Để in ra dãy a đã sắp xếp thông qua dãy c, ta thêm một dãy phụ x có n phần tử.
Sau đó duyệt lại dãy a, với mỗi giá trị a[i] ta đưa giá trị a[i] vào x[c[a[i]]-1] và giảm c[a[i]] đi 1. Tức là khi đưa a[i] vào dãy x thì số lượng phần tử có giá trị a[i] chưa xét đến trong dãy a giảm đi 1 => trừ vào c[a[i]].
Trong ví dụ trên, sau khi sắp xếp, ta xây dựng dãy phụ x như sau:
Xây dựng mảng c: c[0]=2, c[1]=5, c[2]=7, c[3]=9, c[4]=9, c[5]=9, c[6]=10, c[7]=10, c[8]=12. M=8
Duyệt lại dãy a: 1,2,2,6,8,8,0,0,1,1,3,3
i=0, a[i]=1, dãy x trở thành: 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, c[1]=4
i=1, a[i]=2, dãy x trở thành: 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, c[2]=6
i=2, a[i]=2, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 0, 0, 0, c[2]=5
i=3, a[i]=6, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 0, 0, c[6]=9
i=4, a[i]=8, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 0, 8, c[8]=11
i=5, a[i]=8, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 8, 8, c[8]=10
i=6, a[i]=0, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 8, 8, c[0]=1
i=7, a[i]=0, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 8, 8, c[0]=0
i=8, a[i]=1, dãy x trở thành: 0, 0, 0, 1, 1, 2, 2, 0, 0, 6, 8, 8, c[1]=3
i=9, a[i]=1, dãy x trở thành: 0, 0, 1, 1, 1, 2, 2, 0, 0, 6, 8, 8, c[1]=2
i=10, a[i]=3, dãy x trở thành: 0, 0, 1, 1, 1, 2, 2, 0, 3, 6, 8, 8, c[3]=8
i=11, a[i]=3, dãy x trở thành: 0, 0, 1, 1, 1, 2, 2, 3, 3, 6, 8, 8, c[3]=7
Cuối cùng gán lại a=x.

Và đây là chương trình con:

Code:

void sapxep()
    {
      int i,v,x[1000],c[1000];
      for(i=0;i<=m;i++)c[i]=0;//khoi tao day c
      m=0;
      for(i=0;i
      {
            c[a[i]]++;
            if(m
      }
      for(i=0;i<=m;i++)c[i]+=c[i-1];//tinh chi so cuoi
      for(i=0;i
      {
            v=a[i];
            x[c[v]-1]=a[i];
            c[v]--;         
      }
      for(i=0;i
 }

Code như sau:

Code:

#include <stdio.h>
#include <conio.h>
int main()
{
      int n,x,y,i,min,a[100];
      printf("n=");scanf("%d",&n);
      printf("Nhap n so cua mang:\n");
      for(i=0;i<n;i++)
              {
              printf("Phan tu %d: ",i);
              scanf("%d",&a[i]);
              }
      printf("x=");scanf("%d",&x);
      printf("y=");scanf("%d",&y); 
      min=y+1;
      for(i=0;i<n;i++)
      if((min>a[i])&&(a[i]<=y)&&(a[i]>=x))min=a[i];
      if(min==y+1)printf("Khong co phan tu nao nam trong doan [%d,%d]\n",x,y);
      else printf("Phan tu nho nhat can tim la %d\n",min);     
      getch();
      return 0;
}

Code:

Code:

#include <stdio.h>
#include <conio.h>
#define vocuc 999999999
int main()
{
      int n,i,min,max,a[100];
      printf("n=");scanf("%d",&n);
      printf("Nhap n so cua mang:\n");
      for(i=0;i<n;i++)
              {
              printf("Phan tu %d: ",i);
              scanf("%d",&a[i]);
              }
      min=vocuc;
      max=-vocuc;
      for(i=0;i<n;i++)
              {
              if((min>a[i])&&(a[i]>0))min=a[i];
              if((max<a[i])&&(a[i]<0))max=a[i];
              }       
      if(max==-vocuc)printf("Khong co phan tu am trong day\n");
      else printf("Phan tu am lon nhat la %d\n",max);
      if(min==vocuc)printf("Khong co phan tu duong trong day\n");
      else printf("Phan tu duong nho nhat la %d\n",min);
      getch();
      return 0;
}

Code:

Code:

#include <stdio.h>
#include <conio.h>
int main()
{
      int n,i,j,max,tam,sl,cs[100],a[100];
      printf("n=");scanf("%d",&n);
      printf("Nhap n so cua mang:\n");
      for(i=0;i<n;i++)
              {
              printf("Phan tu %d: ",i);
              scanf("%d",&a[i]);
              }
      max=0;sl=0;
      for(i=0;i<n;i++)
              {
              tam=1;
              for(j=i+1;j<n;j++)
              if(a[i]==a[j])tam++;
              if(max<tam)
                        {
                        max=tam;
                        sl=1;
                        cs[0]=i;
                        }
              else if(max==tam)
                        {
                        sl++;
                        cs[sl-1]=i;
                        }     
              }
      printf("So lan xuat hien nhieu nhat la %d\n",max);
      printf("Bao gom: ");
      for(i=0;i<sl;i++)printf("%d ",a[cs[i]]);
      getch();
      return 0;
}

Code:

Code:

#include <stdio.h>
#include <conio.h>
int main()
{
      int n,i,j,tam,a[100];
      printf("n=");scanf("%d",&n);
      printf("Nhap n so cua mang:\n");
      for(i=0;i<n;i++)
              {
              printf("Phan tu %d: ",i);
              scanf("%d",&a[i]);
              }
      //Sap xep theo thu tu tang dan
      for(i=0;i<n;i++)
      for(j=i+1;j<n;j++)
      if(a[i]>a[j])
              {
              tam=a[i];
              a[i]=a[j];
              a[j]=tam;
              }   
      printf("Cac phan tu khac nhau trong day la: %d ",a[0]);
      for(i=1;i<n;i++)
      if(a[i]!=a[i-1])printf("%d ",a[i]);
      getch();
      return 0;
}

Code đây:

Code:

#include
#include
int main()
{
      int n,i,j,k,tam,a[100];
      bool co;
      printf("n=");scanf("%d",&n);
      printf("Nhap n so cua mang:\n");
      for(i=0;i
              {
              printf("Phan tu %d: ",i);
              scanf("%d",&a[i]);
              }
      printf("k=");scanf("%d",&k);
      for(i=0;i
      for(j=i+1;j
      if(a[i]>a[j])
              {
              tam=a[i];
              a[i]=a[j];
              a[j]=tam;
              }
      co=false;   
      if((a[0]>0)&&(a[0]<=k))
              {
              co=true;
              printf("%d ",a[0]);             
              }             
      for(i=1;i
      if((a[i]!=a[i-1])&&(a[i]>0)&&(a[i]<=k))
              {
              co=true;
              printf("%d ",a[i]);
              }
      if(!co)printf("Khong co phan tu nao thuoc doan [1,%d]\n",k);
      getch();
return 0;
}

Code tiếp:

Code:

#include <stdio.h>
#include <conio.h>
int main()
{
      int n,k,i,j,a[100];
      printf("n=");scanf("%d",&n);
      printf("Nhap n so cua mang:\n");
      for(i=0;i<n;i++)
              {
              printf("Phan tu %d: ",i);
              scanf("%d",&a[i]);
              }
      printf("k=");scanf("%d",&k);
      printf("i=");scanf("%d",&i);
      if(n-i<k)printf("Ngoai pham vi cua day!");
      else
            {
            if(n-i==k)n-=k;
            else
                    {
                    for(j=i;j<=n-k;j++)a[j]=a[j+k];
                    n-=k;
                    }
            printf("Day sau khi xoa:\n");
            for(i=0;i<n;i++)printf("%d ",a[i]);
            }
      getch();
      return 0;
}

[quote="peterdrew"]
Xây dựng mảng c: c[0]=2, c[1]=5, c[2]=7, c[3]=9, c[4]=9, c[5]=9, c[6]=10, c[7]=10, c[8]=12. M=8
Duyệt lại dãy a: 1,2,2,6,8,8,0,0,1,1,3,3
i=0, a[i]=1, dãy x trở thành: 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, c[1]=4
i=1, a[i]=2, dãy x trở thành: 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, c[2]=6
i=2, a[i]=2, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 0, 0, 0, c[2]=5
i=3, a[i]=6, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 0, 0, c[6]=9
i=4, a[i]=8, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 0, 8, c[8]=11
i=5, a[i]=8, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 8, 8, c[8]=10
i=6, a[i]=0, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 8, 8, c[0]=1
i=7, a[i]=0, dãy x trở thành: 0, 0, 0, 0, 1, 2, 2, 0, 0, 6, 8, 8, c[0]=0
i=8, a[i]=1, dãy x trở thành: 0, 0, 0, 1, 1, 2, 2, 0, 0, 6, 8, 8, c[1]=3
i=9, a[i]=1, dãy x trở thành: 0, 0, 1, 1, 1, 2, 2, 0, 0, 6, 8, 8, c[1]=2
i=10, a[i]=3, dãy x trở thành: 0, 0, 1, 1, 1, 2, 2, 0, 3, 6, 8, 8, c[3]=8
i=11, a[i]=3, dãy x trở thành: 0, 0, 1, 1, 1, 2, 2, 3, 3, 6, 8, 8, c[3]=7
Cuối cùng gán lại a=x.




-----> cai nay cang xem cang thay thu vi:))
carm own anh nha peter

Đối với yêu cầu sau thì làm thế nào anh peter ơi
[code]

Cho dãy số thực x1, x2,..., xn, trong đó 1  n  1000 và xn  R. Sắp xếp dãy số sao cho các số không âm đứng trước và được sắp xếp theo thứ tự không tăng; các số âm đứng sau và được sắp xếp theo thứ tự không giảm.
Ví dụ, nếu dãy số: 5, -2, 4, -5, 2, -1, 9, 0, -8
cần sắp xếp thành: 9, 5, 3, 2, -8, -5, -2, -1, 0.
Yêu cầu:
Input: Mảng số thực gắn sẵn trong chương trình.
Output: KQ đưa ra màn hình.

[\code]