递归解决方案的任何其他解决方案

Question

我试图找出有多少个长度为 n 的数字，使得每个数字至少比它前后的数字相差 4 smaller/greater。例如：如果n = 5，则此类数字为39518、15951等

下面是解决方案，我可以想出：即使输入大小低至 1000.I 也需要很长时间，我确信，有一些更好的方法可以解决这个问题。如果有人能指点一下，我将不胜感激。

#include <stdio.h>

int out[100000];
int count;
void foo(int *out, int pos_to_fil, int size) {
    if (pos_to_fil == size) {
        count++;
        return;
    }
    int i;
    for (i=0;i<=9;i++) {
        if (pos_to_fil == 0 && i == 0)
            continue;
        if (pos_to_fil >0 && abs(out[pos_to_fil-1] -i) < 4)
            continue;
        out[pos_to_fil] = i;
        foo(out, pos_to_fil + 1, size);
    }
}

int main(void) {
    foo(out, 0, 1000);
    printf("count %d\n", count);
    return 0;
}

Answer 1

也许您可以重写 for header 以使用两个 for 循环使其更短：

int previous = out[pos_to_fill-1];
int i;
//lower than 4
for (i=0;i<previous-4;i++) {
    //... for cycle body
}
//higher than 4
for (i=previous+4;i<=9;i++) {
    //... for cycle body (the same)
}

为了不重复循环 body，如果参数不多，我会将 body 设为函数

注意：未测试，起始i值和条件可能不好，这只是一个想法

Answer 2

简答：不要使用递归，自下而上并使用动态规划。

更长的答案：基本上你正在遍历所有可能的解决方案。唯一增加计数的语句是 count++，因为我们必须增加到一个超过 600 位的数字，这需要一段时间。（即使它不会为每个 count++ 调用一个函数）

所以我们需要以某种方式增加计数，而当时只有 1 个。怎么做？

假设我们已经知道n=2的答案有36种可能。这是否有助于我们计算 n=3 的可能性有多少？不，不是真的，因为我们不知道那 36 个数字是什么。其中一个两位数是 15，可以扩展为 150、151 和 159（3 种可能性）。另一个两位数是 30，可以扩展为 304、305、306、307、308 和 309（6种可能性）。我们显然不能仅仅将 36 乘以某个常数因子来得出 n=3 的解。

但还是有规律的。 30 为下一代产生 6 个新号码这一事实意味着 40、50、60 和所有其他以 [=28= 结尾的两位数] 还将产生 6 个新号码。 15 生成 3 个新号码，所有其他以 5.

结尾的号码也会生成 3 个新号码

那么，如果我们确实从计算 n=2 开始，而不是记住所有 36 个数字，我们记住这个数组：[6, 5, 4, 3, 2, 2, 2, 3, 4, 5] 会怎么样？这个数组意味着我们不知道这 36 个数字到底是什么，但是其中 6 个以 0 结尾，5 个以 1 结尾，4 个以 2 结尾，依此类推在。

现在我们可以通过做一些加法来计算 n=3 的相同数组。 0 可以从 4、5、6、7、8 或 9 中生成。将它们全部相加意味着对于 n=3，将有 2 + 2 + 2 + 3 + 4 + 5 = 18 个以 0 结尾的数字。 n=3 的整个数组是 [18, 16, 14, 12, 15, 16, 15, 18, 20, 22]

不幸的是我不会说 c 但这是 java 中的解决方案。

import java.util.*;                                                         
import java.math.*;                                                         

class BigNum {                                                              


    public static void main (String[] a) {                                  
        Scanner in = new Scanner (System.in);                               
        System.out.println (new BigNum().solve(in.nextInt()));              
    }                                                                       


    BigInteger solve(int n) {                                               
        if (n == 0) return BigInteger.ZERO;                                 
        BigInteger[] counts = new BigInteger[10];                           
        BigInteger[] next = new BigInteger[10];                             
        BigInteger[] temp;                                                  
        Arrays.fill (counts, BigInteger.ONE);                               
        counts[0] = BigInteger.ZERO;                                        

        for (int i = 1; i < n; i++) {                                       
            for (int nextDigit = 0; nextDigit < 10; nextDigit++) {          
                next[nextDigit] = BigInteger.ZERO;                          
                for (int digit = 0; digit < 10; digit++) {                  
                    if (Math.abs (digit - nextDigit) >= 4) {                
                        next[nextDigit] = next[nextDigit].add (counts[digit]);
                    }                                                       
                }                                                           
            }                                                               
            temp = counts;                                                  
            counts = next;                                                  
            next = temp;                                                    
        }                                                                   

        BigInteger sum = BigInteger.ZERO;                                   
        for (BigInteger i : counts) sum = sum.add  (i);                     
        return sum;                                                         
    }                                                                       

}

它有两个数组：counts代表当前世代的数组（上例中n=2），next代表下一代（例子中n=3）。当算法完成计算 next 时，它会交换两个数组，这意味着我们将使用这一代的 next 作为下一代的电流。

它有 3 个 for 循环。外层循环只是计算世代数，根本不使用。 nextDigit计算的是下一代的位数，而digit计算的是当前的位数。当它们至少相隔 4 时，我们进行加法。

如果您想知道，n=1000 的结果确实很大，我花了 165 毫秒来计算：

58671138329570171371420484902268532315073277852051653969830525802838628724212731137694290047005040297045274423072752812252866695216074181116219893270512906481125049825987756071510466880415373048496191391932743103313044071304405218219902707133109687674960299002863298632965964118240544824530569540542700793488917467060307664191744432111922492168260259079355618958225678548171234101375097873342091776899282686824362584042717489292059166512255400959907373002265039739675037774831081921743873154470907306563401667845616259033848968890244196752759640923743592116170624821165172596009768024780906078208584276112384909371479169927564723938874400811048288 possibilities.

递归解决方案的任何其他解决方案

Any other solution for recursive solution

c

algorithm

recursion

dynamic-programming