2 qq 33748682 qq_33748682 于 2016.01.15 17:24 提问

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

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

7个回答

UrHalo
UrHalo   2016.01.15 20: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;
}

UrHalo
UrHalo 追加一行,if( 1 == n) return 1;
接近 2 年之前 回复
caozhy
caozhy   Ds   Rxr 2016.01.15 19: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;
            }
        }
    }
}

caozhy
caozhy   Ds   Rxr 2016.01.15 19:02

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

caozhy
caozhy   Ds   Rxr 2016.01.15 19: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的。

91program
91program   Ds   Rxr 2016.01.15 19:02

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

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

fat_cai_niao
fat_cai_niao   2016.01.15 18:58

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

xl1007
xl1007   2016.01.15 19: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);
    }
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!