C++: Sắp xếp mảng số chẵn trước lẻ sau

Bài toán: Sắp xếp mảng số nguyên sao cho số chẵn đứng trước số lẻ đứng sau, và không dùng mảng phụ.

Ý tưởng: duyệt toàn bộ mảng, gặp phần tử chẵn đầu tiên thì đổi chỗ nó với phần tử đầu tiên, gặp phần tử chẵn thứ hai thì đổi chỗ nó với phần tử ở vị trí thứ hai, lần lượt làm như vậy thì ta sẽ đưa được tất cả các phần tử chẵn ra ngoài cùng.

Ví du: 7 3 5 6 9 8 4 5
Lần 1: đổi số 6 với 7
-- 6 3 5 7 9 8 4 5
Lần 2: đổi số 8 với 3
-- 6 8 5 7 9 3 4 5
Lần 3: đổi số 4 với số 5
-- 6 8 4 7 9 3 5 5

Code: code này hay ở chỗ số lần đổi chỗ sẽ ít hơn so với một số đoạn code khác. (Bạn hãy tự làm và kiểm chứng xem đúng không nhé)

#include <stdio.h>
#include <conio.h>

int main(){
    int *a;
    int n;
    printf("Mang co bao nhieu phan tu ? ");
    scanf("%d",&n);
    a = new int[n];
    for(int i=0;i<n;i++){
        printf("a[%d] = ",i);
        scanf("%d",&a[i]);
    }
    printf("Mang truoc khi sap xep: ");
    for(int i=0;i<n;i++)
        printf("%d  ",a[i]);
    //sap xep
    for(int i=0;i<n-1;i++)
        for (int j=i;j<n;j++){
            if (a[j]%2==0){
                int t = a[i];
                a[i]=a[j];
                a[j]=t;
                break;
            }
        }
    printf("\nMang sau khi sap xep: ");
    for(int i=0;i<n;i++)
        printf("%d  ",a[i]);

}

Code Phiên bản xem từng bước sắp xếp:

#include <stdio.h>
#include <conio.h>

int main(){
    int *a;
    int n;
    printf("Mang co bao nhieu phan tu ? ");
    scanf("%d",&n);
    a = new int[n];
    for(int i=0;i<n;i++){
        printf("a[%d] = ",i);
        scanf("%d",&a[i]);
    }
    printf("Mang truoc khi sap xep: ");
    for(int i=0;i<n;i++)
        printf("%d  ",a[i]);
    //sap xep
        printf("\n");
    for(int i=0;i<n-1 ;i++){
        for (int j=i;j<n;j++){
            if (a[j]%2==0){
                int t = a[i];
                a[i]=a[j];
                a[j]=t;
                break;
            }
        }
        printf("\Lan lap %d: ",i);
        for(int i=0;i<n;i++)
            printf("%d  ",a[i]);
        printf("\n");
    }

    getch();
}

C#: Code xếp N quân hậu (vét cạn) cho đầy đủ lời giải

Trong giải thuật này, mỗi lời giải được ký hiệu bằng một mảng solution[1..n], trong đó solution[i]= j là cột mà quân hậu ở hàng thứ iđứng. Theo tính chất số học của các ô trên bàn cờ n x n, các ô trên các đường chéo cộng chứa ô (i, j) đều có tổng chỉ số hàng với chỉ số cột bằng i+j. Tổng này nhận các giá trị từ 2 đến 2n nên ta đánh số các đường chéo này từ 1 đến 2n-1. Như vậy các ô trên đường chéo cộng thứ nhất có tổng chỉ số dòng và cột là 2, các ô trên đường chéo thứ k có tổng ấy là k+1. Ta dùng một mảng Boolean Ok_plus[1..2n-1] để kí hiệu trạng thái đã có quân hậu nào trên đường chéo cộng thứ k chưa, nghĩa là Ok_plus[k]=True nếu đã có một quân hậu đứng chiếm giữ đường chéo cộng thứ k. Tương tự, các ô trên một đường chéo trừ có hiệu như nhau. Hiệu này nhận giá trị từ 1-n đến n- 1. Đánh số từ 1 đến 2n-1 từ đường chéo có hiệu chỉ số dòng trừ chỉ số cột là 1-n đến đường chéo có hiệu ấy bằng n-1. Khi đó đường chéo trừ thứ k có hiệu chỉ số dòng trừ chỉ số cột là k-n. Ta cũng dùng mảng ok_minus[1..2n-1] để chỉ trạng thái của các đường chéo này.

Giải thuật này cố gắng đặt quân hậu ở dòng thứ i vào cột nào đó, bắt đầu từ dòng thứ nhất (luôn có thể đặt được). Nếu ở dòng thứ i ta đặt quân hậu vào cột thứ j, thì nó khống chế tất cả các ô trong cột thứ j, đường chéo cộng thứ i+j-1, đường chéo trừ thứ i-j+n. Nếu có thể đặt được quân hậu ở dòng i và i = n ta có một lời giải. Nếu đặt được và i < n ta tiếp tục cố gắng đặt quân hậu tiếp theo vào dòng thứ i+1. Nếu không đặt được, ta quay lại nhấc quân hậu ở dòng thứ i-1 và tìm phương án tiếp theo của dòng thứ i-1.

Mã giả

Procedure Try_row(i)

For j=1 To n do

If not ok_row(i) And not ok_col(j) And not ok_plus(i+j-1) And not ok_minus(i-j+n) then

{

solution(i)=j;

ok_col(j)=True;

ok_plus(i+j-1)=True;

ok_minus(i-j+n)=True;

If i<n then

try_row(i+1)

ELSE print_solution();

ok_row(i)=False;

ok_col(j)=False;

ok_plus(i+j-1)=False;

ok_minus(i-j+n)=False;

}

Thủ tục tìm tất cả các lời giải của bài toán n hậu chỉ bao gồm một lời gọi Try_row(1):

Procedure n_queen(n);

Call Try_row(1);

Video Code C#:

C#: Thuật toán tìm đường ngắn nhất Bellman-Ford

Thuật toán

function BellmanFord(danh_sách_đỉnh, danh_sách_cung, nguồn)
   // hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh sách cung
   // hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh, 
   // sao cho các giá trị đỉnh_liền_trước sẽ lưu lại các đường đi ngắn nhất.

   // bước 1: khởi tạo đồ thị
   for each v in danh_sách_đỉnh:
       if v is nguồn then khoảng_cách(v):= 0
       else khoảng_cách(v):= vô cùng
       đỉnh_liền_trước(v):= null
   
   // bước 2: kết nạp cạnh
   for i from 1 to size(danh_sách_đỉnh):       
       for each (u,v) in danh_sách_cung:
           if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v):
               khoảng_cách(v):= khoảng_cách(u) + trọng_số(u,v)
               đỉnh_liền_trước(v):= u

   // bước 3: kiểm tra chu trình âm
   for each (u,v) in danh_sách_cung:
       if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v):
           error "Đồ thị chứa chu trình âm"

Tham khảo: 

1/ Wikipedia Tiếng Việt
2/ Wikipedia Tiếng Anh

Video:

Phần 1:


Phần 2:

C#: Bài toán hôn nhân bền vững

Thuật toán: 

function stableMatching {
    Khởi tạo m ∈ M và w ∈ W bằng độc thân
    while ∃ người đàn ông độc thân m vẫn còn có người phụ nữ w để cầu hôn {
       w = người phụ nữ m thích nhất mà vẫn chưa cầu hôn
       if w độc thân
         (m, w) trở thành đã đính hôn
       else một cặp (m', w) đã đính hôn
         if w thích m to m'
           (m, w) trở thành đã đính hôn
           m' trở thành độc thân
         else
           (m', w) vẫn đã đính hôn
    }
}

Xem chi tiết: https://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_h%C3%B4n_nh%C3%A2n_b%E1%BB%81n_v%E1%BB%AFng
Video hướng dẫn: 

C#: Bài toán 8 (N) quân hậu bằng thuật toán Quay lui

Thuật toán Quay lui Tìm lời giải cho bài toán 8 (hoặc N) quân hậu 

(chịu khó dịch thành tiếng Việt nhé)
1) Start in the left most column
2) If all queens are placed
    return true
3) Try all rows in the current column.  Do following for every tried row.
    a) If the queen can be placed safely in this row then mark this [row,
        column] as part of the solution and recursively check if placing
        queen here leads to a solution.
    b) If placing queen in [row, column] leads to a solution then return
        true.
    c) If placing queen doesn't lead to a solution then umark this [row,
        column] (Backtrack) and go to step (a) to try other rows.
3) If all rows have been tried and nothing worked, return false to trigger
    back tracking

Video hướng dẫn lập trình:

C#: Giải trò chơi Sudoku bằng thuật toán quay lui

Sudoku là một loại trò chơi lôgic và cách chơi là điền số từ 1 đến 9 vào những ô trống sao cho mỗi cột dọc, mỗi hàng ngang, mỗi phân vùng nhỏ (ô 3x3) có đủ các số từ 1 đến 9 mà không được lặp lại. Bảng câu đố hình vuông, mỗi chiều có 9 ô nhỏ, hợp thành 9 cột, 9 hàng và được chia thành 9 ô lớn 3x3.
Giả sử có bàn cờ ban đầu như bên dưới:



Một bàn cờ Sudoku

Đáp án cho bàn cờ này như sau:



Sử dụng giải thuật quay lui để giải bài toán này, ta có đoạn mã giả như sau:

function backtrack(position){     if (isEndOfGrid == true){ // Empty cells filled. Solution found. Abort         return true;     }     foreach (x from 1 ... 9){         grid[position] = x;         if (gridIsValid == true){ // Check for collisions             if (backtrack(nextPosition) == true){ // Move to next empty cell                 return true; // Empty cells filled. Solution found. Abort.             }         }     }     grid[position] = NULL; // Empties cell     return false; //Solution not found. Backtrack. }

Thuật toán quay lui thực hiện các bước như sau:



Chương trình Demo Giải trò chơi Sudoku bằng thuật toán quay lui do Vương Huỳnh Long viết:

Các bài tập chuyên đề chia để trị cơ bản

Bài liên quan:

1. Cách  trình bày mô tả một thuật toán chia để trị
2. Trình bày cách tính độ phức tạp của một đoạn chương trình
3. Các bài tập chuyên đề chia để trị cơ bản

#include <stdio.h>


int Tong (int *a,int n){
    if (n==1)
        return a[0];
    else
        return a[n-1]+Tong(a,n-1);

}
int TongLe(int *a,int n){
    if (n==1){
        if (a[0]%2==0)
            return 0;
        else
            return a[0];
    }
    else if (a[n-1]%2==0)
        return TongLe(a,n-1)+0;
    else
        return TongLe(a,n-1)+a[n-1];
}

int doicho(int &a,int &b){
    int t = a;
    a = b;
    b = t;
}

void DaoMang(int *a,int i,int j){
 //   if (j-i+1==1)
   //     return;
    if(j-i+1==2)
        doicho(a[i],a[j]);
    else if(j-i+1>2){
        doicho(a[i],a[j]);
        DaoMang(a,i+1,j-1);
    }
}

void inMang(int *a,int n){
    for(int i=0;i<n;i++)
        printf("%d  ",a[i]);
}
int main(){
    int *a =new int[6] {5,8,1,4,6,7};
    printf("%d  ",Tong(a,6));
    printf("\n\n---\n\n");
    printf("mang truoc khi dao: \n");
    inMang(a,6);
    printf("\nmag sau khi dao:\n");
    DaoMang(a,0,5);
    inMang(a,6);
        return 0;
}

Cấu trúc dữ liệu Cây Tổng Quát

#include <stdio.h>
#include <conio.h>
#define MaxLength 10
#define NIL -1
typedef int Node;
typedef char DataType;
typedef struct Tree{
 DataType    Data[MaxLength];
 Node  Parent[MaxLength];
 int MaxNode;
};


void MakeNullTree(Tree &T){
    T.MaxNode=0;
}
int EmptyTree (Tree T){
    return (T.MaxNode == 0);
}

Node Parent (Node n,Tree T){
    if(EmptyTree(T)  ||  n>T.MaxNode-1)
        return NIL;
    else
        return T.Parent[n];
}
DataType LabelNode(Node n, Tree T){
    if(!EmptyTree(T) && n<=T.MaxNode-1)
            return T.Data[n];
}
Node Root(Tree T){
    if(EmptyTree(T))
        return NIL;
    else
        return 0;
}
Node LeftMostChild (Node n, Tree T){
    if (n<0) return NIL;
    for(Node i=n+1;i<T.MaxNode;i++){
        if(Parent(i,T) ==n)
            return i;
    }
    return NIL;
}

Node RightSibling(Node n, Tree T){
    if(n<0) return NIL;
    Node parent = Parent(n,T);
    for(Node i=n+1;i<T.MaxNode;i++){
        if(Parent(i,T)==parent)
            return i;
    }
    return NIL;
}

void PreOrder(Node n, Tree T){
    if(!EmptyTree(T)){
        printf("%c  ",LabelNode(n,T));
        Node i = LeftMostChild(n,T);
        while(i!=NIL){
            PreOrder(i,T);
            i=RightSibling(i,T);
        }
    }
}

void InOrder(Node n, Tree T){
    Node i = LeftMostChild(n,T);
    if(i!=NIL)
        InOrder(i,T);
    printf("%c  ",LabelNode(n,T));
    i=RightSibling(i,T);
    while(i!=NIL){
        InOrder(i,T);
        i=RightSibling(i,T);
    }
}

void PostOrder(Node n,Tree T){
    Node i=LeftMostChild(n,T);
    while (i!=NIL){
        PostOrder(i,T);
        i=RightSibling(i,T);
    }
    printf("%c  ",LabelNode(n,T));
}

int Depth(Node n, Tree T){
    Node p=Parent(n,T);
    if(p==-1)
        return 0;
    return 1+Depth(p,T);
}

int OrderNode(Node n, Tree T){
    int bac=0;
    for(Node i=n+1;i<T.MaxNode;i++)
        bac+=(Parent(i,T)==n);
    return bac;
}

int OrderTree(Tree T){
    int m=0;
    for(Node i=0;i<T.MaxNode;i++){
        int n=OrderNode(i,T);
        if (m<n)
            m=n;
    }
    return m;
}

int IsLeaf(Node n, Tree T){
    return (LeftMostChild(n,T)==NIL);
}

int Height(Tree T){
    int h=0;
    for(Node i = 0; i<T.MaxNode;i++)
        if(IsLeaf(i,T)){
            int d=Depth(i,T);
            if (h<d)
                h=d;
        }
    return h;
}

int IsAncestor(Node a, Node d, Tree T){
    while (d!=NIL){
        if (a==d)
            return 1;
        else
            d=Parent(d,T);
    }
    return 0;
}


Node CommonAncestor(Node n,Node m, Tree T){
    int dn=Depth(n,T) , dm=Depth(m,T);
    if (Parent(n,T)== Parent(m,T)) return Parent(n,T);
    if (Parent(n,T)== m) return m;
    if (Parent(m,T)== n) return n;
    if (dn > dm)
        CommonAncestor(Parent(n,T),m,T);
    else if (dn<dm)
        CommonAncestor(n,Parent(m,T),T);
    else
        CommonAncestor(Parent(n,T),Parent(m,T),T);

}

int main(){
    Tree T;
    MakeNullTree(T);
    char data[]={'A','B','C','D','E','F','G','H','I','J'};
    int parent[]={-1,  0,  0,  1,  1,  4,  4,  4,  2,  2 };
    for(int i=0;i<10;i++){
        T.Data[i]=  data[i];
        T.Parent[i]=parent[i];
    }
    T.MaxNode=10;
    printf("Duyet tien tu: "); PreOrder(0,T);
    printf("\nDuyet trung tu: "); InOrder(0,T);
    printf("\nDuyet hau tu: "); PostOrder(0,T);
    printf("\nDo sau cua nut D: %d",Depth(3,T));
    printf("\nBac cua nut A = %d va nut E = %d",OrderNode(0,T),OrderNode(4,T));
    printf("\nBac cua cay T = %d",OrderTree(T));
    printf("\nIsLeaf(B) ? %d ", IsLeaf(1,T));
    printf("\nIsLeaf(J) ? %d ", IsLeaf(9,T));
    printf("\nChieu cao cay T = %d",Height(T));
    printf("\nIsAncestor(B,H) ? %d",IsAncestor(1,7,T));
    printf("\nIsAncestor(D,H) ? %d",IsAncestor(3,7,T));
    printf("\nIsAncestor(D,A) ? %d",IsAncestor(3,0,T));
    printf("\nIsAncestor(D,D) ? %d",IsAncestor(3,3,T));
    printf("\nCommonAncestor(F,B) ? %c",LabelNode(CommonAncestor(5,1,T),T));
    printf("\nCommonAncestor(D,F) ? %c",LabelNode(CommonAncestor(3,5,T),T));
    printf("\nCommonAncestor(F,D) ? %c",LabelNode(CommonAncestor(5,3,T),T));
    printf("\nCommonAncestor(D,J) ? %c",LabelNode(CommonAncestor(3,8,T),T));
    return 0;
}