qq_33748682
2016-01-15 09:24
采纳率: 33.3%
浏览 1.6k
已采纳

C语言算法问题,大神帮忙啊

输入一个整数N,分解成奇数的和,有多少种分解方法,例如,5可以分解成1+1+1+1+1,1+1+3,1+3+1,3+1+1,5这五种分解方法

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

7条回答 默认 最新

  • UrHalo 2016-01-15 12:24
    已采纳

    unsigned int calc(unsigned int n){
    unsigned int i, sum = 0;
    if( 0 == n) return 0;
    for( i = 1; i <= n; i += 2){
    sum += calc( n-i);
    }
    return sum;
    }

    打赏 评论
  • 小胖头 2016-01-15 10:58

    其实是一种排列组合。其他的数也一样,先吧小于等于N的奇数分出来。去掉一和本身。剩余的进行排列组合图片

    打赏 评论
  • threenewbee 2016-01-15 11:02

    用C#写一个,C语言思路一样,递归

     using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace ConsoleApplication1
    {
        class Program
        {
            static void Main(string[] args)
            {
                int i = 5;
                foreach (int x in Enumerable.Range(1, i).Where(x => x % 2 == 1))
                    foreach (var item in foo(i, new int[] { x })) 
                        Console.WriteLine(string.Join(",", item));
            }
    
            static IEnumerable<IEnumerable<int>> foo(int sum, IEnumerable<int> seed)
            {
                if (seed.Sum() == sum) { yield return seed; yield break; }
                for (int i = 1; i <= sum - seed.Sum(); i += 2)
                {
                    foreach (var item in foo(sum, seed.Concat(new int[] { i })))
                        yield return item;
                }
            }
        }
    }
    
    
    打赏 评论
  • threenewbee 2016-01-15 11:02

    1,1,1,1,1
    1,1,3
    1,3,1
    3,1,1
    5
    Press any key to continue . . .

    打赏 评论
  • 91program 2016-01-15 11:02

    首先,你要将小于整数N的所有奇数找出来。
    然后,循环做加法测试和是否是整数N。如果是,则记录;如果不是,则继续下一组。

    但是 1+1+3,1+3+1,3+1+1 也可以算做 3 种,这有点变态。

    打赏 评论
  • threenewbee 2016-01-15 11:03

    1,1,1,1,1,1,1,1,1,1
    1,1,1,1,1,1,1,3
    1,1,1,1,1,1,3,1
    1,1,1,1,1,3,1,1
    1,1,1,1,1,5
    1,1,1,1,3,1,1,1
    1,1,1,1,3,3
    1,1,1,1,5,1
    1,1,1,3,1,1,1,1
    1,1,1,3,1,3
    1,1,1,3,3,1
    1,1,1,5,1,1
    1,1,1,7
    1,1,3,1,1,1,1,1
    1,1,3,1,1,3
    1,1,3,1,3,1
    1,1,3,3,1,1
    1,1,3,5
    1,1,5,1,1,1
    1,1,5,3
    1,1,7,1
    1,3,1,1,1,1,1,1
    1,3,1,1,1,3
    1,3,1,1,3,1
    1,3,1,3,1,1
    1,3,1,5
    1,3,3,1,1,1
    1,3,3,3
    1,3,5,1
    1,5,1,1,1,1
    1,5,1,3
    1,5,3,1
    1,7,1,1
    1,9
    3,1,1,1,1,1,1,1
    3,1,1,1,1,3
    3,1,1,1,3,1
    3,1,1,3,1,1
    3,1,1,5
    3,1,3,1,1,1
    3,1,3,3
    3,1,5,1
    3,3,1,1,1,1
    3,3,1,3
    3,3,3,1
    3,5,1,1
    3,7
    5,1,1,1,1,1
    5,1,1,3
    5,1,3,1
    5,3,1,1
    5,5
    7,1,1,1
    7,3
    9,1
    Press any key to continue . . .

    这是10的。

    打赏 评论
  • xl1007 2016-01-15 11:03

    用递归方法解决:(我是学java 的,写了一个java的实现方法,思路是一样的,你可以看看)

    //测试方法
    public static void test(List<String> resultList, String str,int a){
        str = str.length() > 0 ? str + "+" : str;
        int b;
        for(int i = 0; i < a; i = i + 1){
            b = a - i;
            if(isOdd(i) && isOdd(b)){
                resultList.add(str +  i + "+" + b);
            }
            if(isOdd(i) && b > 1){
                test(resultList, str  + i, b);
            }
            if(i == 0 && str.length() == 0 && isOdd(a)){
                resultList.add(str + a);
            }
        }
    }
    //判断奇偶 奇数:true,偶数:true
    public static boolean isOdd(int a){
        return (a & 1) != 0;
    }
    //主方法
    public static void main(String args[]){
        List<String> list = new ArrayList<String>();
        //调用方法
        test(list, "",8);
        //打印结果
        for(String str : list){
            System.out.println(str);
        }
    }
    
    打赏 评论

相关推荐 更多相似问题