求个计算问题的算法

Question

本帖最后由 hky5_com 于 2013-03-22 21:54:01 编辑

Answer 1

是否允许数字重复？
比如  5，100，195，10 A =200 输出 100, 100。如果是不重复，参考
http://bbs.csdn.net/topics/380259947
组合后求和，看有没有符合的。

Answer 2

    static class Program
    {
        [STAThread]
        static void Main()
        {
            Ar(new int[] { 5, 100, 195, 10 }, 200);
        }
        //先列出递归原理
        //static void Ar(int[] ar, int g)
        //{
        //    int size = ar.Length;
        //    for (int x = 0; x < size; x++)
        //    {
        //        for (int y = x + 1; y < size; y++)
        //        {
        //            for (int z = y + 1; z < size; z++)
        //            {
        //                if (x + y + z == g)
        //                    return true;
        //                else if (x + y + z > g)//结束
        //                    break;
        //                //for (int a = z + 1; a < size; a++)
        //                //...
        //            }
        //        }
        //    }
        //}        //开始点
        static void Ar(int[] array, int target)
        {
            //结果
            int[] result = new int[array.Length];
            if (Ar(array, target, ref result, 0, 0, 0))
            {
                //成功
                Console.Write("成功：");
                for (int i = 0; i < result.Length; i++)
                {
                    if (i > 0)
                        Console.Write("+");
                    Console.Write(result[i]);
                }
                Console.Write("=" + target);
                Console.WriteLine();
                Console.Read();
            }
            else
            {
                result = new int[0];
                //失败
                Console.Write("失败");
                Console.Read();
            }
        }
        static bool Ar(int[] array, int target, ref int[] result, int index, int depth, int aggregate)
        {
            int size = array.Length;
            int val;
            for (int i = index; i < size; i++)
            {
                val = array[i] + aggregate;
                if (val > target)
                    break;
                else if (val == target)
                {
                    result[depth] = array[i];
                    Array.Resize(ref result, depth + 1);
                    return true;
                }
                result[depth] = array[i];
                if (Ar(array, target, ref result, i + 1, depth + 1, val))
                    return true;
            }
            return false;
        }
    }

Answer 3

    static class Program
    {
        [STAThread]
        static void Main()
        {
            Ar(new int[] { 5, 100, 195, 10 }, 200);
        }
        //先列出递归原理
        //static void Ar(int[] ar, int g)
        //{
        //    int size = ar.Length;
        //    for (int x = 0; x < size; x++)
        //    {
        //        for (int y = x + 1; y < size; y++)
        //        {
        //            for (int z = y + 1; z < size; z++)
        //            {
        //                if (x + y + z == g)
        //                    return true;
        //                else if (x + y + z > g)//结束
        //                    break;
        //                //for (int a = z + 1; a < size; a++)
        //                //...
        //            }
        //        }
        //    }
        //}        //开始点
        static void Ar(int[] array, int target)
        {
            //结果
            int[] result = new int[array.Length];
            if (Ar(ref result, new ArInfo { Array = array, Target = target, Aggregate = 0, Depth = 0, Index = 0 }))
            {
                //成功
                Console.Write("成功：");
                for (int i = 0; i < result.Length; i++)
                {
                    if (i > 0)
                        Console.Write("+");
                    Console.Write(result[i]);
                }
                Console.Write("=" + target);
                Console.WriteLine();
                Console.Read();
            }
            else
            {
                result = new int[0];
                //失败
                Console.Write("失败");
                Console.Read();
            }
        }
        public class ArInfo
        {
            public int Index;
            public int Depth;
            public int Aggregate;
            public int[] Array;
            public int Target;
        }
        static bool Ar(ref int[] result, ArInfo info)
        {
            int size = info.Array.Length;
            int aggregate;
            for (int i = info.Index; i < size; i++)
            {
                aggregate = info.Array[i] + info.Aggregate;
                if (aggregate > info.Target)
                    break;
                else if (aggregate == info.Target)
                {
                    result[info.Depth] = info.Array[i];
                    Array.Resize(ref result, info.Depth + 1);
                    return true;
                }
                result[info.Depth] = info.Array[i];
                if (Ar(ref result, new ArInfo { Array = info.Array, Target = info.Target, Aggregate = aggregate, Depth = info.Depth + 1, Index = i + 1 }))
                    return true;
            }
            return false;
        }
    }

Answer 4

搞错了是：
                if (aggregate > info.Target)
                    continue;

Answer 5

错了，是        public static bool Ar(int[] array, int target, out int[] result)
        {
            int size = array.Length;
            result = new int[size];            StackInfo info = new StackInfo { Index = 0, Depth = 0, Aggregate = 0 };            Stack<StackInfo> stack = new Stack<StackInfo>();
            stack.Push(info);            int aggregate;
            while (stack.Count > 0)
            {
                info = stack.Pop();
                for (int i = info.Index; i < size; i++)
                {
                    aggregate = info.Aggregate + array[i];
                    if (aggregate > target)
                        continue;                    result[info.Depth] = array[i];
                    if (aggregate == target)
                    {
                        Array.Resize(ref result, info.Depth + 1);
                        return true;
                    }
                    stack.Push(new StackInfo { Index = info.Index + 1, Depth = info.Depth, Aggregate = info.Aggregate });
                    stack.Push(new StackInfo { Index = i + 1, Depth = info.Depth + 1, Aggregate = aggregate });
                    break;
                }
            }
            result = null;
            return false;
        }

Answer 6

我这个方法可以实现你的要求：
没有做异常处理。
Console.WriteLine("请输入总数：");
int total = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("请输入数值的个数：");
int a = Convert.ToInt32(Console.ReadLine());
int[] shuZ = new int[a];
for (int i = 0; i < shuZ.Length; i++) //把用户输入的数存到数组中；
{
Console.WriteLine("请输入第{0}个数：",i+1);
int b = Convert.ToInt32(Console.ReadLine());
shuZ[i] = b;
}
int sum = 0;
for (int i = 0; i < shuZ.Length; i++)//求输入所有数值之和；
{
sum += shuZ[i];
}
if (total != sum)
{
Console.WriteLine("0");
}
else
{
for (int i = 0; i < shuZ.Length; i++)
{
Console.Write("{0}\t",shuZ [i]);
}
}
Console.ReadKey();
楼主，看看是不是你想要的结果？