已知 N 個大小在 1至 K 的數的和是M，求有多少種 N 的結果，這個演算法如何算有大神指導么
已知 N>1, K>1, N*K>M>N
public static int getResult(int n,int k,int m){
}
uj5u.com熱心網友回復：
r(n,s,k,m) = sum(r(n-1,j,k,m-j)), 1≤j≤K, j≤m-j≤kgetResult(n,k,m) = r(n,1,k,m)
uj5u.com熱心網友回復：
最笨的做法，遍歷整個陣列，求出合適的解。為了防止重復解答，約定整個陣列按照非遞減方式排列
//從當前的陣列跳轉到下一個陣列
boolean increaseArray(int ary_value[], int ary_size, int ary_max_value) {
for (int i=ary_size-1; i>=0; i--) {
if (ary_value[i]<ary_max_value) {
ary_value[i]= ary_value[i]+1;
return true;
} else {
ary_value[i] = 1;
}
}
return false;
}
//判斷陣列是否為非遞減陣列
boolean isAvailableArray(int ary_value[], int ary_size) {
for （int i=1; i<ary_size; i++) {
if (ary_value[i]<ary_value[i-1] ) {
return false;
}
}
return true;
}
//計算陣列和
boolean getSummary(int ary_value[]; int ary_size) {
int result=0;
for (int i=0; i<ary_size; i++) {
result = result+ ary_value[i];
}
return result;
}
//然后，主體程式部分
int getCountOfMethod(int target = M, int size=N, int max_num= K) {
int result_count = 0;
int[size] num;
for (int i=0; i<size; i++) {
num[i] = 1;
}
do {
if (isAvailableArray(num, size)) {
if (getSummary(num, size)== target) {
result_count = result_count+1;
}
}
} while (increaseArray(num, size, max_num)== true)
return result_count;
}
至于基于純數學角度的計算公式，還需要思考
uj5u.com熱心網友回復：
上面的方法確實比較“笨”，主要是體現在時間復雜度上。如代碼所示，需要執行(K^N)次increaseArray()的動作，而每次increaseArray()動作里面平均需要執行N/2次進位，
以及每次increaseArray()完畢之后需要執行isAvailableArray動作(平均包含N/2次比較)，以及getSummary動作(包含N次求和)
則總的時間復雜度為O(N*(K^N))
但是在此方法的基礎上，我們其實是可以讓它更快一點的。
此前的方法，可以等價為一個N位長度的K進制數的遍歷和各個數位求和的問題。
其實，我們可以先找出一個"最小"的符合條件的K進制數a0，然后在此基礎上直接找下一個(即第二小的)符合條件的K進制數a1，再在此基礎上尋找a2, a3,...一直到找不到下一個進制數為止。
這里的"符合條件"指的是
1) 各個數位之和=M
2)各個數位的內容介于min_value(在這里是1)以及max_value(在這里是K)
3)高位數字<=低位數字
-----------------------------------------------------------------------
先思考怎么找到一個"最小的"符合條件的數字a0。
這個方法很簡單，先用min_value鋪滿各個數位，然后從低位往高位，依次改成用max_value(這里是K)，直到整個數位的和>=M，然后再調整最后一個修改的高位，使得數位和=M。
這里可能有兩種例外: N*min_value>M和N*max_value<M，這兩者表示找不到a0，當然就沒有合適解。
-----------------------------------------------------------------------
再思考怎么從某一個合適的解a推匯出下一個"最小的"合適解b。
很顯然，要讓和不變，一定有一個數位要減少，同時也一定有一個數位要增加，這樣才可能保證總和不變。
為了讓b>a，意味著增加值的數位一定相比減少至的數位處于”更高位"。
于是，可以提出如下的演算法：
在a=v[0]v[1]v[2]...v[N]，
找出最低位的"可以增加值"的數v[x]，
然后再在v[x+1]...v[N]中，找出最高位的"可以減少值"的數v[y]，
然后v[x]=v[x]+1, v[y]=v[y]-1。
這樣構造出來的數自然滿足和不變性和最小性原則
然后就是對"可以增加值"的v[x]以及可以減少值的v[y]的界定。
很顯然，如果有下標x<y的數位v[x]+1<=v[y]-1，則意味著v[x]可以+1而v[y]可以-1。
所以，我們可以為數字v[0]v[1]...v[N]建立陣列d[0]d[1]...,d[N-1]，其中的d[i]=v[i+1]-v[i]。
然后從后往前找第1個d[x]，使得d[x]+d[x+1]+...+d[N-1]>=2，則意味著v[x]可以加1。
再從d[x]開始向從前往后找第1個d[t]，使得d[x]+d[x+1]+...+d[t]>=2，則意味著v[t+1]可以減1。
然后來看一下大概的時間復雜度。為了找到一個解，我們需要經過N/2+N/4次的查找，所以總的時間與總的解的數量有關。
如果有A個解，則總的解復雜度為O(A*N)。
憑直覺，我覺得這種演算法應該要快一點。
---------------------------------------------------------------------------
以下是大致代碼
//獲取第一個解(回傳false表示沒有找到。)
boolean getFirstAnswer(int ary_value[], int ary_size, int min_value, int max_value, int target_value) {
for (int i=0; i<ary_size; i++) {
ary_value[i] = min_value;
}
int sum_value = min_value* ary_size;
if (sum_value>target_value) {
return false;
} else if (sum_value=https://bbs.csdn.net/topics/=target_value) {
return true;
} else {
for (int i= ary_size-1; i>=0; i--) {
ary_value[i]= max_value;
sum_value=https://bbs.csdn.net/topics/ sum_value+max_value-min_value;
if (sum_value>=target_value) {
ary_value[i]=ary_value[i]-(sum_value-target_value);
return true;
}
}
return false;
}
}
//計算各個元素與前一元素的差
void calcDifference(int[] ary_value, int ary_size, int[] difference) {
for (int i= ary_size-2; i>=0; i--) {
difference[i]= ary_value[i+1]-ary_value[i];
}
}
//查找最小的可以增加的元素編號，回傳-1表示沒有找到。
int getMinIncreaseableIndex(int[] difference, int ary_size) {
int diff = 0;
for (int i= ary_size-2; i>=0; i++) {
diff = diff + difference[i];
if (diff>=2) {
return i;
}
}
return -1;
}
//在指定位置之后，查找最大的可以減少數字的位置編號。（-1表示沒有找到，在本演算法中，不可能出現該狀況)
int getMaxDecreaseableIndex(int[] difference, int ary_size, int firstIndex) {
diff = 0;
for (int i= firstIndex; i<ary_size-1; i++) {
diff = diff+difference[i];
if (diff>=2) {
return diff+1;
}
}
return -1;
}
//獲取下一個"最小的"解, false表示沒有找到有效解
boolean getNextAnswer(int[] ary_value, int ary_size, int[] difference) {
int firstIndex= getMinIncreaseableIndex(difference, ary_size);
if (firstIndex<0) {
return false;
}
int lastIndex = getMaxDecreaseableIndex(difference, ary_size, firstIndex);
if (lastIndex<0) {
return false;
}
ary_value[firstIndex]=ary_value[firstIndex]+1;
//調整firstIndex+1到firstIndex，以及firstIndex到firstIndex-1的difference
if ((firstIndex>=0) && (firstIndex<ary_size-1)) {
difference[firstIndex]=difference[firstIndex]-1;
}
if ((firstIndex-1>=0) && (firstIndex-1<ary_size-1)) {
difference[firstIndex-1]=difference[firstIndex-1]+1;
}
ary_value[lastIndex]=ary_value[lastIndex]-1;
//調整lastIndex+1到lastIndex,以及lastIndex到lastIndex-1的difference
if ((lastIndex>=0) && (lastIndex<ary_size-1)) {
difference[lastIndex]=difference[lastIndex]+1;
}
if ((lastIndex-1>=0) && (lastIndex-1<ary_size-1)) {
difference[lastIndex-1]=difference[lastIndex-1]-1;
}
return true;
}
//最后，主體程式
int getCountOfMethod(int target = M, int size=N, int min_num=1, int max_num= K) {
int result_count = 0;
int[size] num;
int[size-1] difference;
if (getFirstAnswer(num[], size, min_num, max_num, target)) {
result_count = result_count+1;
calcDifference(num, size, difference);
while (getNextAnswer(num, size, difference) do {
result_count=result_count+1;
}
}
return result_count;
}
心目中的例子大致如下:(min=1, max=6, 數字數量=7, 目標值20)
First Answer:
111 1277
然后依次搜索到以下解
111 1367
111 1457
111 1466
111 1556
111 2456
111 2555
111 3455
111 4445
112 3445
112 4444
113 3444
122 3444
123 3344
133 3334
223 3334
233 3333
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85347.html
標籤：數據結構與算法
上一篇：求助，修改用戶名后無法登入！！！