太公分猪肉

发表评论 阅读评论

今天在群里讨论一题,两个长度为 n 的数组a,b ,交换各个元素,使 a 的和 与 b的和 最接近。
伪代码为 sum(a) - sum(b) 趋向于 0
这个算法不知道叫什么名字,姑且先 称之为 太公分猪肉 吧。
下面分别用AS3和C++来实现。

太公分猪肉之C++

#include <iostream>
using namespace std;

#define n 10
int a[] = { 2, 6, 8, 10, 30, 30, 50, 50, 60, 100 };
int b[] = { 15,53,46,8,59,43,5,79,55,553 };

void swap(int &a,int &b)//两数交换
{
    a=a^b;
    b=a^b;
    a=a^b;
}
// a 于b 合并到buf, a,b长度都为len
void fillArray(int *buf, int * a, int * b)
{
    for (int i = 0; i < n; i++)
    {
        buf[i*2]=a[i];
        buf[i*2+1]=b[i];

    }
    cout<<"合并后:";
    for (int i = 0; i < n*2; i++)
    {
        cout<<buf[i]<<" ";
    }
    cout<<endl;
}

// 打印数组
void printArray(int *arr)
{
    for (int i = 0; i < n; i++)
    {
        cout << * (arr + i) << ' ';
    }
}

//冒泡排序, 从小到大
void sort(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            if (arr[i] > arr[j])
            {
                swap(arr[i],arr[j]);
            }
        }
    }
}
// 求和
int sum(int* arr)
{
    int tmp=n;
    int s = 0;
    while (--tmp >= 0)
    {
        s += *(arr + tmp);
    }
    return s;
}
int main()
{
    cout<<"计算前:n";
    cout << "a: "; printArray(a); cout << " = " << sum(a) << 'n';
    cout << "b: "; printArray(b); cout << " = " << sum(b) << 'n';

    int * two = new int[2 * n];
    fillArray(two,a,b);//先合并
    sort(two, 2 * n);

    int indexA = n - 1;
    int indexB = n - 1;
    int sumA = 0;
    int sumB = 0;
    int i = 0;

    for(i = 2 * n - 1;i>= 0; i--)
    {
        bool full = false;
        if(indexA < 0)
        {
            b[indexB--] = two[i];
            full = true;
        }
        else if(indexB < 0)
        {
            a[indexA--] = two[i];
            full = true;
        }
        if(full) 
            continue;
        if(sumA <sumB)
        {
            a[indexA--] = two[i];
            sumA+=two[i];
        }
        else
        {
            b[indexB--] = two[i];
            sumB+=two[i];
        }
    }

    cout<<"计算后:n";
    cout << "a: "; printArray(a);   cout << " = " << sum(a) << 'n';
    cout << "b: "; printArray(b);   cout << " = " << sum(b) << 'n';
    return 0;
}

太公分猪肉之AS3

package 
{
    import flash.display.Sprite;

    /**
     * www.litefeel.com
     * lite3@qq.com
     * @author lite3
     */
    public class EqualizeTwoArray extends Sprite
    {
        private var n:int = 10;
        private var a:Array = [2, 6, 8, 10, 30, 30, 50, 50, 60, 100];
        private var b:Array = [0, 1, 2,  3,  4,  6,  6,  7,  7,   8];
        public function EqualizeTwoArray() 
        {
            trace("计算前:");
            trace("a: ", a, " = ", sum(a));
            trace("b: ", b, " = ", sum(b));

            var two:Array = a.concat(b);    // 合并两个数组
            two.sort(Array.NUMERIC);        // 排序
            var indexA:int = n - 1;
            var indexB:int = n - 1;
            var sumA:int = 0;
            var sumB:int = 0;

            for(var i:int = 2 * n - 1;i>= 0; i--)
            {
                var full:Boolean = false; // 数组元素个数是否 超过n个
                if(indexA < 0)
                {
                    b[indexB--] = two[i];
                    full = true;
                }else if(indexB < 0)
                {
                    a[indexA--] = two[i]
                    full = true;
                }
                if (full) continue;

                // 从大到小分
                if(sumA <sumB)
                {
                    a[indexA--] = two[i];
                    sumA+=two[i];
                }else
                {
                    b[indexB--] = two[i];
                    sumB+=two[i];
                }
            }

            trace("计算后:");
            trace("a: ", a, " = ", sum(a));
            trace("b: ", b, " = ", sum(b));
        }

        // 数组求和
        private function sum(arr:Array):int
        {
            var s:int = 0;
            for each(var v:int in arr)
            {
                s += v;
            }
            return s;
        }

    }

}

计算结果:

计算前:
a:  2,6,8,10,30,30,50,50,60,100  =  346
b:  0,1,2,3,4,6,6,7,7,8  =  44
计算后:
a:  1,2,3,6,6,7,30,30,50,60  =  195
b:  0,2,4,6,7,8,8,10,50,100  =  195
标签: , ,

  1. | |

    楼主写的不是C++而是C。。。。。浑然的一个过程化的程序。。。

  2. | |

    @xuexuankr
    看看确实是的, 虽然用了C++的 cout 但思想还是过程化的,C++ 没深入,惭愧啊 :shock:

  3. | |

    楼主交个朋友吧~~~这个博客值得收藏啊。。。

  4. | |

    @xuexuankr
    很高兴交你这个朋友。O(∩_∩)O哈哈~ :grin: :razz:

  1. 本文目前尚无任何 trackbacks 和 pingbacks.
回到顶部