问题描述
- C语言算法问题，大神帮忙啊
-
输入一个整数N，分解成奇数的和，有多少种分解方法，例如，5可以分解成1+1+1+1+1,1+1+3,1+3+1,3+1+1,5这五种分解方法
解决方案
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;
}
解决方案二：
用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;
}
}
}
}
解决方案三：
1,1,1,1,1
1,1,3
1,3,1
3,1,1
5
Press any key to continue . . .
解决方案四：
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的。
解决方案五：
首先，你要将小于整数N的所有奇数找出来。
然后，循环做加法测试和是否是整数N。如果是，则记录；如果不是，则继续下一组。
但是 1+1+3,1+3+1,3+1+1 也可以算做 3 种，这有点变态。
解决方案六：
其实是一种排列组合。其他的数也一样，先吧小于等于N的奇数分出来。去掉一和本身。剩余的进行排列组合
解决方案七：
用递归方法解决：（我是学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);
}
}