Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    Document 1

    Uploaded by

    Lê Quyên Võ
    The document contains code snippets for several algorithms related to combinatorics and recursion in C/C++ including: 1) Generating all combinations of n items into k groups using backtracking recursion. 2) Solving the N-Queens problem using backtracking to place queens on a chessboard such that no two queens attack each other. 3) Code to solve the Towers of Hanoi recursive problem of moving disks between rods subject to rules of only moving one disk at a time and never placing a larger disk on top of a smaller one.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Document 1

    Uploaded by

    Lê Quyên Võ
    22 views14 pages
    The document contains code snippets for several algorithms related to combinatorics and recursion in C/C++ including: 1) Generating all combinations of n items into k groups using backtracking recursion. 2) Solving the N-Queens problem using backtracking to place queens on a chessboard such that no two queens attack each other. 3) Code to solve the Towers of Hanoi recursive problem of moving disks between rods subject to rules of only moving one disk at a time and never placing a larger disk on top of a smaller one.

    Original Title

    Document1

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains code snippets for several algorithms related to combinatorics and recursion in C/C++ including: 1) Generating all combinations of n items into k groups using backtracking recursion. 2) Solving the N-Queens problem using backtracking to place queens on a chessboard such that no two queens attack each other. 3) Code to solve the Towers of Hanoi recursive problem of moving disks between rods subject to rules of only moving one disk at a time and never placing a larger disk on top of a smaller one.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    22 views14 pages

    Document 1

    Uploaded by

    Lê Quyên Võ
    The document contains code snippets for several algorithms related to combinatorics and recursion in C/C++ including: 1) Generating all combinations of n items into k groups using backtracking recursion. 2) Solving the N-Queens problem using backtracking to place queens on a chessboard such that no two queens attack each other. 3) Code to solve the Towers of Hanoi recursive problem of moving disks between rods subject to rules of only moving one disk at a time and never placing a larger disk on top of a smaller one.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 14

    1.

    PP Nghiệm sinh
    #include<bits/stdc++.h>
    using namespace std;

    int n, k;

    bool isLast(int x[]) {


    if(x[0] != k)
    return false;
    for(int i = 1; i < n; i++)
    if(x[i] != 0)
    return false;
    return true;
    }

    void Print(int x[]) {


    for(int i = 0; i < n; i++)
    printf("%d ", x[i]);
    printf("\n");
    }

    void ToNext(int x[]) {


    int sum = k;
    int i = 0;
    while(sum > 0) {
    sum -= x[i];
    i++;
    }
    i -= 2;
    x[i]++;
    sum = k;
    for(int j = 0; j <= i; j++)
    sum -= x[j];
    for(int j = i + 1; j < n; j++)
    x[j] = 0;
    x[n - 1] = sum;
    }

    void Generate(int n, int k) {


    int x[n];
    for(int i = 0; i < n - 1; i++)
    x[i] = 0;
    x[n - 1] = k;
    Print(x);
    while(!isLast(x)) {
    ToNext(x);
    Print(x);
    }
    }
    int main() {
    scanf("%d %d", &n, &k);
    Generate(n, k);
    }

    2. PP Nghiem dequy(quay lui)


    #include<stdio.h>

    int n, k;
    int x[1010];

    void Print() {
    for(int i = 0; i < n; i++)
    printf("%d ", x[i]);
    printf("\n");
    }

    void Try(int i, int sum) {


    if(i == n) {
    if(sum == k)
    Print();
    return;
    }
    for(int j = 0; j <= k; j++) {
    x[i] = j;
    Try(i + 1, sum + j);
    }
    }

    int main() {
    scanf("%d %d", &n, &k);
    Try(0, 0);
    }

    3. Btoan con hậu


    #include <bits/stdc++.h>
    #define MAX 20
    using namespace std;
    int A[MAX];
    bool Check(int x, int y);
    void Result(int n);
    void Try(int i, int n);
    bool Check(int x,int y){
    for(int i = 1; i < x ; i++)
    if(A[i] == y || abs(i-x) == abs(A[i] - y) )
    return false;
    return true;
    }
    void Result(int n){
    for(int i = 1;i <= n; i++)
    cout<<A[i]<<" ";
    cout<<"\n";
    }
    void Try(int i,int n){
    for(int j = 1; j <= n; j++){
    if(Check(i,j)){
    A[i] = j;
    if(i == n) Result(n);
    Try(i+1,n);
    }
    }
    }
    int main(){
    int n;
    cin>>n;
    Try(1,n);
    }

    4. Thap Hanoi
    #include<stdio.h>
    void move(char a,char c);
    void hanoi(int n,char a,char b,char c);
    int main(){
    int n;
    scanf("%d",&n);
    char a='A',b='B',c='C';
    hanoi(n,a,b,c);
    return 0;
    }
    void move(char a,char c){
    printf("%c------>%c\n",a,c);
    }
    void hanoi(int n,char a,char b,char c){
    if(n==1) move(a,c);
    else {
    hanoi(n-1,a,c,b);
    hanoi(1,a,b,c);
    hanoi(n-1,b,a,c);
    }
    }

    5. Hoan vi khong lap


    #include <stdio.h>
    int d=0;
    void out(int s[],int n){
    printf("%d: ",++d);
    for(int i=1;i<=n;i++)
    printf("%d",s[i]);
    printf("\n");
    }
    void hv(int i, int s[],int b[],int n){
    for(int j=1;j<=n;j++){
    if(b[j]==1) {
    s[i]=j;
    b[j]=0;
    if (i==n) out(s,n);
    else hv(i+1,s,b,n);
    b[j]=1;
    }
    }
    }
    int main(){
    int n;
    printf("input n= ");
    scanf("%d",&n);
    int b[n+1],s[n+1];
    for (int i=1;i<=n;i++)
    b[i]=1;
    hv(1,s,b,n);
    return 0;
    }
    6. Tap con Phuong phap quay lui
    #include <stdio.h>

    void out(int b[], int n);


    void Try(int i, int a[], int n, int k);
    int d = 0;

    int main()
    {
    int n,k;
    scanf("%d%d", &n, &k);
    int a[k+1]; a[0] = 0;
    Try(1,a,n,k);
    return 0;
    }

    void out(int a[], int n)


    {
    printf("%d: ",++d);
    for (int i = 1; i<=n; i++) printf("%d ",a[i]);
    printf("\n");
    }

    void Try(int i, int a[], int n, int k)


    {
    for (int j = a[i-1]+1; j<=n-k+i; j++)
    {
    if (j<=n+k-i) a[i] = j;
    if (i==k) out(a,k);
    else Try(i+1,a,n,k);
    }
    }

    7. Tập con phương pháp sinh


    #include <stdio.h>

    void init(int a[], int k);


    void out(int a[], int k);
    int islast(int a[], int k, int n);
    void gen(int a[], int k, int n);
    void method(int a[], int k, int n);
    int d = 0;

    int main()
    {
    int n;
    int k;
    printf("input n = ");
    scanf("%d",&n);
    printf("input k = ");
    scanf("%d",&k);
    int a[k+1];
    method(a,k,n);
    return 0;
    }

    void init(int a[], int k)


    {
    for (int i = 1; i<=k; i++) a[i] = i;
    }

    void out(int a[], int k)


    {
    printf("%d: ",++d);
    for (int i = 1; i<=k; i++) printf("%d ",a[i]);
    printf("\n");
    }

    int islast(int a[], int k, int n)


    {
    for (int i = 1; i<=k; i++)
    if(a[i]!=n-k+i) return 0;
    return 1;
    }
    void gen(int a[], int k, int n)
    {
    int i = k;
    while (a[i]==n-k+i) i--;
    a[i] = a[i] + 1;
    for (int j = i+1; j<=k; j++)
    a[j] = a[i] + j - i;
    }

    void method(int a[], int k, int n)


    {
    init(a,k);
    out(a,k);
    int stop = islast(a,k,n);
    while (stop == 0)
    {
    gen(a,k,n);
    out(a,k);
    stop = islast(a,k,n);
    }
    }

    8. Tất cả tập con từ 1.. n phần tử


    #include <stdio.h>
    void out(int b[], int n);
    void Try(int i, int a[], int n, int k);
    int d = 0;

    int main()
    {
    int n,k;
    scanf("%d", &n);
    int a[k+1]; a[0] = 0;
    printf("%d: \n", ++d);
    for (k = 1; k <= n; k++)
    Try(1,a,n,k);
    return 0;
    }

    void out(int a[], int n)


    {
    printf("%d: ",++d);
    for (int i = 1; i<=n; i++) printf("%d ",a[i]);
    printf("\n");
    }

    void Try(int i, int a[], int n, int k)


    {
    for (int j = a[i-1]+1; j<=n-k+i; j++)
    {
    if (j<=n+k-i) a[i] = j;
    if (i==k) out(a,k);
    else Try(i+1,a,n,k);
    }
    }

    9. Truy hoi
    #include<bits/stdc++.h>
    using namespace std;

    bool isCalc[100100];
    int A[100100];

    void Init() {
    A[0] = 5;
    A[1] = 9;
    A[2] = 12;
    isCalc[0] = isCalc[1] = isCalc[2] = true;
    }

    int calc(int n) {
    if(n < 0)
    return 0;
    if(isCalc[n])
    return A[n];
    isCalc[n] = true;
    return A[n] = 8 * calc(n - 1) - 21 * calc(n - 2) + 19 * calc(n - 3);
    }

    int main() {
    Init();
    int n;
    scanf("%d", &n);
    printf("%d", calc(n));
    }

    You might also like