从哪里开始解决这个问题 [英] Where to start for solve this exercise in c

问题描述

您好我求助于您的帮助，目的是指示我，解决此练习必须遵循的步骤明确表示我不是要求解决问题



给定一组{1 ... N}我们可以将它分成两个子集，它们的总和相同，例如对于N = 3：

Hello I resort to your help with the intention of indicating me, what are the steps that I must follow to solve this exercise make it clear that I am not asking for the solution to the problem

Given a set {1...N} We can divide it into two subsets that their sum give the same, for example for N = 3:

{1,2} = {3}

N = 7的另一个例子：

Another example with N = 7:

{1,6,7} = {2,3,4,5}
{2,5,7} = {1,3,4,6}
{3,4,7} = {1,2,5,6}
{1,2,4,7} = {3,5,6}

给定N，计算我们可以为这个属性设置子集的方式，对于N = 3，我们已经看到有可能;对于N = 7，我们有4种可能性。制作一个递归算法，解决任何0< N< 39.

Given an N, calculate how many ways we can make the subsets for this property is fulfilled, for N = 3 we have seen that there is a possibility; for N = 7 we have 4 possibilities. Make a recursive algorithm that solves for any 0 < N < 39.

Example input:
7
The function must be given:
3
Example input 2:
3
Example output 2
1

欢迎任何援助



编辑

any aid would be welcome

edit

#include<stdio.h>

int count( int S[], int m, int n )
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    if (m <=0 && n >= 1)
        return 0;
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int main(void)
{
    int arr[] = {1,6,7};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 7));
    return 0;
}

但给我的结果不正确



来源： http://en.wikipedia.org/wiki/Change-making_problem [ ^ ]

推荐答案

I承认你要求解决方案的一般步骤而不是现成的解决方案。



我假设你知道什么是递归算法 [ ^ ]是。以下是愚蠢的蛮力的布局[ ^ ]递归算法来解决这个问题。



设置：

从用户输入中读取 N 。

创建一个集合对于{1..N}， M 并使用这些值初始化它。

创建两个空集合 L 和 R 。

用 M ， L 和 R 。



递归：

一种作为参数的方法：

收集 M 包含尚未分布式值。

集合 L 和 R 包含已经分配的值。



如果 M 为空：

- 对中的值求和L 和 R 。

- 比较总和。如果相等，请将 L 和 R 添加到有效结果中（例如将其打印到控制台）。

- 返回。



否则（ M 不为空）：

- 从 M 中取出下一个值 x 。

- 插入 x 进入 L 并使用这些新集合调用递归方法。

- 删除 x 从 L ，将其插入 R 并调用递归方法这些新系列。

- 从 R 中删除​​ x 并将其重新放入 M 。

- 退货。





你可以通过削减蛮力搜索的一些路径，使它更聪明一些。例如。对于初始 M = {1,2,3,4}，在递归时 L = {1,2}， R = {}和 M = {3,4}您不必继续递归因为...？ （为什么以及如何留给你作为练习。）

I acknowledge that you asked for the general steps to the solution and not for a ready made solution.

I assume you know what a recursive algorithm[^] is. The following is a layout for a dumb brute-force[^] recursive algorithm to solve this problem.

Set-up:
Read N from user-input.
Create a collection M for {1..N} and initialize it with these values.
Create two empty collections L and R for the two subsets.
Call the recursive method with M, L and R.

Recursion:
One method that takes as arguments:
Collection M containing the not-yet distributed values.
Collections L and R containing the already distributed values.

If M is empty:
- Sum the values in L and R.
- Compare the sums. If equal, add L and R to the valid results (e.g. print it to the console).
- Return.

Else (M is not empty):
- Take the next value x out of M.
- Insert x into L and call the recursive method with these new collections.
- Remove x from L, insert it into R and call the recursive method with these new collections.
- Remove x from R and put it back into M.
- Return.


You could make it a bit smarter by cutting some paths of the brute-force-search. E.g. for an initial M = {1,2,3,4}, at the point of the recursion where L = {1,2}, R = { } and M = {3,4} you wouldn't have to continue the recursion because ...? (The why and how left as an exercise for you.)

这篇关于从哪里开始解决这个问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！