Tìm số các số có k chữ số chỉ gồm 4 chữ số trên, sao cho tổng các chữ số là N

John_Smith · October 6, 2015, 2:27pm

Mình đang có bài tập mà chưa biết cách giải mong các bạn giúp

Cho tập gồm 4 chữ số 0, 1, 2, 5. Với hai số k và N cho trước, hãy tìm số các số có k chữ số chỉ gồm 4 chữ số trên, sao cho tổng các chữ số là N.
Ví dụ, với k=3 và N=5, danh sách các số là: 500, 221, 212, 122. Như vậy có tất cả 4 số.
Lập trình giải bài toán bằng sử dụng Stack hay Queue.

ltd · October 6, 2015, 2:27pm

Để tránh topic này trở thành topic hỏi bai tập thì @John_Smith đưa ra một vài ý tưởng xem, hoặc dự đoán sẽ làm thế nào để mọi người hướng dẫn dễ hơn hoặc bắt đầu hỏi bằng những vấn đề nhỏ của bài toán, thay vì hỏi toàn bộ bài tập

John_Smith · October 6, 2015, 2:31pm

Hiện tại e đã làm được bài toán bằng cách vét cạn. Nhưng chưa biết làm sao để làm bằng stack

John_Smith · October 6, 2015, 2:34pm

Code vét cạn của e

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.Scanner;



public class vetcan {
    static int n,k;
    static int [] arr = {0,1,2,5};
    public static int sum(int [] a)
    {
        int sum = 0;
        for (int b : a)
        {
            sum += b;
        }
        return sum;
    }
  public static void binary (int []a,int i)
    {
        
        int v;
        for ( v = 0; v < 4 ; v++)
        {
            a[i] = arr[v];
            if (i < k-1) binary(a, i+1);
            else if (sum(a) == n && a[0] != 0) 
            {
                for (int b: a)
                {
                    System.out.print(b);
                }
                System.out.println("");
            }
        }
    }
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.print("Nhap k: ");
       k = sc.nextInt();
       System.out.print("Nhap N: ");
       n = sc.nextInt();
        int [] a = new int[k];
        binary(a, 0);   
    }
}

Nguyen_Dong · October 6, 2015, 2:56pm

Có lẽ dùng stack hơi khó với bài này, dùng Queue với thuật toán loang:

bạn sẽ gọi hàm

gen(i, x) tức là gen chữ số thứ i, với tổng là x (gần giống quy hoạch động). Thì gen(i, x) sẽ gọi gen(i - 1, x - digit) với digit = {0, 1, 2, 5}. Độ phức tạp là O(N*k)