Xin hỏi thuật toán bài "Liệt kê các số có 3 chữ số sao cho tổng các chữ số của nó bằng số n ( 1 <= n <= 27) cho trước"

[blogthanhlap]

Liệt kê các số có 3 chữ số sao cho tổng các chữ số của nó bằng số n ( 1 <= n <= 27)
cho trước.
input: 3
output: 101 111 120 201 210 300

View more random threads:

• in ra dãy số nhị phân của 1 sô
• cứu bài tính tiền rất mini
• Mảng động
• Ai giúp em với được ko ạ. Đang gấp. Tks AE
• mách giùm với !
• Em cần các anh chị hướng dẫn bài tập
• Bài tập về Đa năng hóa toán tử ?
• Bác nào giúp em sửa lổi xuất dử liệu DSLK em voi
• microsoft visual studio 2010
• cộng 2 số lớn, không giới hạn chữ số.

[admin]

Liệt kê các số có 3 chữ số sao cho tổng các chữ số của nó bằng số n ( 1 <= n <= 27)
cho trước.
input: 3
output: 101 111 120 201 210 300

code này của mình dùng cách vét hết các giá trị.
Ai dùng quay lui hay thuật toán gì hay thì post lên mình tham khảo với nhé!!!!
#include"stdio.h"
#include"conio.h"
#include"math.h"
int tong(int n)
{
int s=0;
while(n!=0)
{
s=s+n%10;
n=n/10;
}
return s;
}
int main()
{
int i,n;
printf("nhap vao tong n:
");
scanf("%d",&n);
for(i=100;i<=999;i++)
{
if(tong(i)==n)
printf("%d ",i);
}
getch();

}

[anhhungan]

- có 2 lối giải , 1 lối thiên về toán học sẽ đạt được tối ưu về thuật toán cơ mà khó (mình cũng lười nghĩ) .Còn 1 lối thiên về tin học :

- loại thô thiển nhất: bạn cho 1 vòng for từ 100 - > 999 , kiểm tra xem số nào thỏa mãn tổng các chữ số bằng n thì in ra. chú ý là bạn cần một hàm tính tổng các chữ số của 1 số x bất kỳ, cái này thì phải động não 1 chút

- loại thứ 2 cải tiến đi, dùng thuật toán "quay lui". nói về cái thuật toán quay lui thì có lẽ hơi dài dòng bạn tự seach vậy, khi nào làm xong loại trên muốn nâng cao thì bạn làm loại này

[s2_cloud_s2]

Mình dùng quay lui nó như vầy

#include <iostream>
using namespace std;

const int M = 3;
int array[M],n;

void print()	{
	
	for(int i = 0; i < M; i++)
	{
		if(array[0] != 0)
			cout << array[i];
	}
	cout << "  ";
	
}

int tong()	{
	return array[0]+array[1]+array[2];
}

void backtracking(int i)	{
	
	for(int j = 0; j <= 9; j++)
	{
		array[i] = j;
			
		if(i == M-1)
		{
			if(tong() == n)
				print();
		}
		else
			backtracking(i+1);
	}
	
}

int main()	{
	
	cin >> n;
	backtracking(0);
	
}