按降序将给定数字除以一组整数的方法数-yiteyi-C++库

给定两个数字 $a$ 和 $m$ .任务是找出 A. 可以用一个集合来表示 ${n_1, n_2, ...., n_c}$ 以至于 $a >= n_1 > n_2 > ... > n_m > 0$ 这些数字之和等于 A. 而且 $1 <= c <= m$ （集合的最大大小不能超过 M ).

null

例子 :

输入：a=4，m=4 输出 : 2 –> ({4}, {3, 1}) 笔记：{2，2}不是有效集，因为值不是按降序排列的

输入：a=7，m=5 输出 : 5 –> ({7}, {6, 1}, {5, 2}, {4, 3}, {4, 2, 1})

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 这个问题可以通过使用递归方法进行分治来解决，该方法遵循以下条件：

如果 A. 等于零，则找到一个解。
如果a>0且m==0，则此集合违反条件，因为无法在集合中添加更多值。
如果已经对给定的 A. , M 和prev（当前集合中包含的最后一个值）返回该值。
从…开始循环我 = A. 直到0，如果我 < 上，如果我们包括我在当前集合中，并返回它。

以下是上述方法的实施情况：

                     # Python3 code to calculate the number of ways                   
                     # in which a given number can be represented                   
                     # as set of finite numbers                   
                             
                     # Import function to initialize the dictionary                   
                     from                               collections                               import                               defaultdict                   
                             
                     # Initialize dictionary which is used                   
                     # to check if given solution is already                   
                     # visited or not to avoid                   
                     # calculating it again                   
                     visited                               =                               defaultdict(                               lambda                               :                               False                               )                   
                             
                     # Initialize dictionary which is used to                   
                     # store the number of ways in which solution                   
                     # can be obtained for given values                   
                     numWays                               =                               defaultdict(                               lambda                               :                               0                               )                   
                             
                     # This function returns the total number                   
                     # of sets which satisfy given criteria                   
                     # a --> number to be divided into sets                   
                     # m --> maximum possible size of the set                   
                     # x --> previously selected value                   
                     def                               countNumOfWays(a, m, prev):                   
                             
                                         # number is divided properly and                   
                                         # hence solution is obtained                   
                                         if                               a                               =                               =                               0                               :                   
                                         return                               1                   
                             
                                         # Solution can't be obtained                   
                                         elif                               a >                               0                               and                               m                               =                               =                               0                               :                   
                                         return                               0                   
                             
                                         # Return the solution if it has                   
                                         # already been calculated                   
                                         elif                               visited[(a, m, prev)]                               =                               =                               True                               :                   
                                         return                               numWays[(a, m, prev)]                   
                             
                                         else                               :                   
                                         visited[(a, m, prev)]                               =                               True                   
                             
                                         for                               i                               in                               range                               (a,                               -                               1                               ,                               -                               1                               ):                   
                                         # Continue only if current value is                   
                                         # smaller compared to previous value                   
                                         if                               i < prev:                   
                                         numWays[(a,m,prev)]                               +                               =                               countNumOfWays(a                               -                               i,m                               -                               1                               ,i)                   
                             
                                         return                               numWays[(a, m, prev)]                   
                             
                     # Values of 'a' and 'm' for which                   
                     # solution is to be found                   
                     # MAX_CONST is extremely large value                   
                     # used for first comparison in the function                   
                     a, m, MAX_CONST                               =                               7                               ,                               5                               ,                               10                               *                               *                               5                   
                     print                               (countNumOfWays(a, m, MAX_CONST))                   

输出：

时间复杂性： O（a*log（a））

文章版权归作者所有，未经允许请勿转载。

THE END

Python