演算法題目：從0-24可重復選擇10個數字之和等于24的排列組合有多少種？要求用java寫，在線等
uj5u.com熱心網友回復：
這也是動態規劃？uj5u.com熱心網友回復：
從大到小，剪枝遍歷uj5u.com熱心網友回復：
可以保存中間結果，那跟動態規劃差不多了uj5u.com熱心網友回復：
用深度優先遍歷+剪枝，代碼如下
public class Test {
/**
* 可取的數量
*/
private static int MAX_LEN = 10;
/**
* 可選擇的最大值
*/
private static int MAX_VALUE = 24;
/**
* 預期值
*/
private static int VALUE = 24;
/**
* 結果
*/
private static long RESULT;
/**
* 儲存結果、驗證
*/
//private static int[] results = new int[MAX_LEN];
public static void main(String[] args) {
next(0, 0);
System.out.println(RESULT);
}
public static void next(int sum, int currentLen){
if (currentLen + 1 == MAX_LEN) {
if (VALUE - sum > 0) {
RESULT++;
//results[currentLen] = VALUE - sum;
//print();
}
return;
}
for (int i = 0; i < MAX_VALUE; i++) {
//results[currentLen] = i;
long currentResult = RESULT;
next(sum + i, currentLen + 1);
if (currentResult == RESULT) {
return;
}
}
}
/* private static void print(){
for (int result : results) {
System.out.print(result + " ");
}
System.out.println();
}*/
}
uj5u.com熱心網友回復：
可重復選取呀:
即可為: 0 0 0 0 0 0 0 0 0 24,
也可為: 0 0 0 0 0 0 0 0 1 23,
排列組合呀:
0 0 0 0 0 0 0 0 1 23, 也可為 1 0 0 0 0 0 0 0 0 23, 也可為 0 1 0 0 0 0 0 0 0 23,
這是一個數學計算的問題，不需要代碼遍歷什么的。
uj5u.com熱心網友回復：
我的演算法不能重復取值嗎
uj5u.com熱心網友回復：
答案是240嗎uj5u.com熱心網友回復：
答案錯了應該是10的24方我是這樣考慮問題
設函式F（x）為從0-24可重復選擇10個數字之和等于X的解種數
f1=10（10個位置選個1出來所以10種）
f2= 的話是再f1的所有組合中抽出一種 比如 1 0 0... 然后十個位置上任選一個位置+1那數字之和就是等于2了 所以種數應該是10*10
f3 = 的話是再f2的所有組合中抽出一種 然后十個位置上任選一個位置+1那數字之和就是等于3了 所以種數應該是發f(2)*10
...
fn=10^n
uj5u.com熱心網友回復：
結果不對。
/**
* 可取的數量
*/
static const int MAX_LEN = 10;
/**
* 可選擇的最大值
*/
static const int MAX_VALUE = 24;
/**
* 預期值
*/
static const int VALUE = 24;
/**
* 結果
*/
static long RESULT =0;
// 迭代次數
static int RN_ = 0;
/**
* 儲存結果、驗證
*/
// static int[] results = new int[MAX_LEN];
void next_(int sum, int currentLen){
if (currentLen + 1 == MAX_LEN) {
if (VALUE - sum > 0) {
RESULT++;
//results[currentLen] = VALUE - sum;
//print();
}
RN_++;
return;
}
for (int i = 0; i < MAX_VALUE; i++) {
//results[currentLen] = i;
long currentResult = RESULT;
next_(sum + i, currentLen + 1);
if (currentResult == RESULT) {
return;
}
}
}
// 暴力遍歷
int rp()
{
int s = 0;
#define N_N(_n) for (int n_##_n = 0; n_##_n <= MAX_VALUE; n_##_n++)
#define N_s(_n, _p) int sum_##_n = sum_##_p + n_##_n;
#define B_s(_n) if (sum_##_n == VALUE) { s++; RN_++; break; }
N_N(0)
{
int sum_0 = n_0;
B_s(0);
N_N(1)
{
N_s(1, 0);
B_s(1);
N_N(2)
{
N_s(2, 1);
B_s(2);
N_N(3)
{
N_s(3, 2);
B_s(3);
N_N(4)
{
N_s(4, 3);
B_s(4);
N_N(5)
{
N_s(5, 4);
B_s(5);
N_N(6)
{
N_s(6, 5);
B_s(6);
N_N(7)
{
N_s(7, 6);
B_s(7);
N_N(8)
{
N_s(8, 7);
B_s(8);
N_N(9)
{
N_s(9, 8);
B_s(9);
RN_++;
}
}
}
}
}
}
}
}
}
};
return s;
}
//數學推理
// 階乘
int fact(int n)
{
int r = 1;
for (int m = 1; m <= n; m++)
r *= m;
return r;
}
// 計算指定陣列的排列方式數量
// 注意重復數字
// 應當為：全不同情況下總數量階乘/重疊數量的階乘
int st(int* v, int n)
{
int* nb = new int[n];
for (int i = 0; i < n; i++)
nb[i] = 1;
for (int i = 0; i < n; i++)
{
for (int m = 0; m < i; m++)
{
if (v[i] == v[m])
{
nb[m]++;
break;
}
}
}
int r= fact(n) ;
for (int i = 0; i < n; i++)
if (nb[i] != 1)
r /= fact(nb[i]);
return r;
}
// 從f-t范圍內選取n個數，使其和值為v，可重復選取
// 求其各組合
int sn(int f, int t, int n, int v, int* cm, int cmsize, int* cm_r)
{
RN_++;
if (n==0)
{
if (v == 0)
{
int nst = st(cm, cmsize); // 發現組合，求組合的可能排列方式
*cm_r += nst;
return 1;
}
return 0;
}
if (f > t) return 0;
if (f > v) return 0;
int a = f, ae = f + t/n;
int r = 0;
for (; a <= ae; a++)
{
cm[cmsize-n] = a;
r += sn(a , t, n - 1, v - a, cm, cmsize, cm_r);
}
return r;
}
int ma()
{
int cm[10] = {0}, cm_r = 0;
int r = sn(0, 24, 10, 24, cm, 10, &cm_r);
return cm_r;
}
int _tmain(int argc, _TCHAR* argv[])
{
// ma
std::cout << "ma\t" << (RN_ = 0, ma()); // 38567100
std::cout << "\t迭代次數: " << RN_ << endl; //57723
// 暴力遍歷
std::cout << "暴力遍歷:\t" << (RN_ = 0, rp()); // 38567100
std::cout << "\t迭代次數: " << RN_ << endl; // 131128140
// 錯誤
std::cout << "next_(錯誤)\t" << (RN_=0, next_(0, 0), RESULT) ; // 28048800
std::cout << "\t迭代次數: " << RN_ << endl; // 38567091
}
uj5u.com熱心網友回復：
嗯，少了個等號，沒有取到24這個值
uj5u.com熱心網友回復：
不知道LZ所說的"排列組合"到底是排列還是組合。如果是排列的話,1,0,0,0,0,0,0,0,0,23與0,1,0,0,0,0,0,0,0,23是不同的，如果是組合則兩者是相同的。轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/82647.html
標籤：數據結構與算法
下一篇：testlink的日志實作