Java-银行账户资金的平分问题?

UI设计界面 UI设计界面 主题:1059 回复:2190

Java-银行账户资金的平分问题?

清晨说ぺ晚安 发布于 2017-06-01 字数 371 浏览 1087 回复 7

有23个帐户,拥有不同资金(可随意设置),现要求将23个帐户资金平分,规则如下:
从帐户中转出金额,得扣转出金额的6%手续费
输入帐户,得扣转入金额的5%手续费。

例如:
从A帐户中取出1000元,则要从1000中扣除6%金额,实得金额为940元。
再将940元转入B帐户,则要扣除940 * 5%手续费。

问你最后均分的金额是多少,总共花费多少手续费?寻一个高效的算法

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(7

偏爱自由 2017-10-10 7 楼

选定其中一个账户作为汇总账户,将剩下22人的钱全部回到这个账户,汇总后的钱平分(这里的平分,汇总用户不会扣除入账费用,所以要好好算一下)后再分别打到22个账户中。

我的方法能实现完全平分,算法复杂度也不高,0(n)。但是转入转出的金额较大,扣除的手续费就会比较多,不能保证最终平分到23个用户的金额是所有方法中最多的。

晚风撩人 2017-09-20 6 楼

使用堆排序的方法试试,从小到大排,如果前者比后者小则平分,不交换。依次循环,直到相等。

偏爱自由 2017-09-18 5 楼

说下我的思路:
假设最后各帐户金额为 X
那么存在以下等式:
帐户资金总和 - 23 X = 所有 ((Xi - X) 6% + (Xi - X) 94% 5% ) 和
其中 Xi 为帐户资金大于 X的帐户
令 G = 所有(Xi - X) 6% + (Xi - X) 94% 5% ) 和
avg = ( 帐户资金总和 - G ) / 23
当G为0时, avg 为平均值,应该是最大
那么取X为最初平均值时,G应该最小,从而根据G算出的avg也比真正X要
大,这样一直逼近,直到 G - (sum - n
X) < 0.000001

include <stdio.h>

include <iostream>

include <math.h>

define N 23

using namespace std;

float getValue(float data[],float x)
{
float result =0;
for(int i =0; i < N; i++)
{
if ( data[i] > x)
{
result += (data[i] - x) 0.06 + (data[i] - x) 0.94 * 0.05;
}
}

return result;
}

int main()
{
float data[N];
float result;
float avg =0,sum = 0;
float charge = 0;
float flag = 0;

for(int i = 0; i < N; i++)
{
cout<<"data["<<i<<"]=";
cin>>data[i];
sum += data[i];
}

avg = sum / N;

do
{
result = getValue(data,avg);
charge = sum - N * avg;
avg = ( sum - result) / N;
flag = abs((int)(result - charge));

}while(flag > 0.000001);

cout<<"avg is: "<<avg<<endl;
cout<<endl;

return 0;
}

泛泛之交 2017-09-13 4 楼

说说我的理解吧,题目需要对账户进行平均,假设最终平均值为avg,实际上就是所有金额高于avg的账户的金额需要扣手续费,而低于avg的无需扣,整个题目就转化为寻找avg和数组的分界点的问题。
首先还是对账户进行排序,同时计算总额sum,可以确定的是avg的范围在sum0.940.95/23~sum/23之间,找到这个区间内的账户,分别尝试,应该很快能得到结果。
算法复杂度O(N*lgN),主要是排序所耗

灵芸 2017-08-26 3 楼

我想的是这样的。
第一种算法:账户按金额从小到大排序,然后data[22]和data[0]平分,data[21]和data[1]平分……
每一轮平分后判断是否全部均分,若不均,则继续。
第二种算法:
也是先从小到大排序,
1、data[0]与data[1]平分,
data[1]-x=data[0]+0.89x;
分配结果:data[0]=data[1]<data[2]
2、data[0]、data[1]与data[2]平分,
data[2]-2x=data[0]+0.89x=data[1]+0.89x;
分配结果:data[0]=data[1]=data[2]<data[3]
3、data[0]、data[1]、data[2]与data[3]平分,
data[3]-3x=data[0]+0.89x=data[1]+0.89x=data[2]+0.89x;
........................
如果是这样,那么算法时间复杂度就只是你的排序算法时间复杂度 + O(n)了。
原则就是 if (a<b<c) then (b-x=a+0.89x<c)

清晨说ぺ晚安 2017-07-23 2 楼

假设原来账户里的钱为 x1。。。x23, 平分后每个人的钱为y。
构件目标函数 z = sum(y-xi)* 5%(入) + sum(xi-y)*6% (出) (0<=y<=min(xi))

再加上其他的条件,然后用线性规划求z的最小值,这个高中学过。 也有现成的解线性规划的算法,java,c,c++ 都有相应的包。也可以参考 各种数值算法的参考书。

偏爱自由 2017-06-20 1 楼

代发布:

换一种思路:只有三种账户,一种是转出金钱的账户,另一种是转入金钱的账户,最后一种是不转出也不转入的账户

设最终每一个账户的平均资金为A,则账户X1,X2……X23里的钱要么大于A,要么小于A。(等于A可以视同Xm账户里的钱比A多0元,或者视同为Xm账户里的钱比A少0元)。则大于A的账户转出钱,小于A的账户转入钱。由此可将上述问题归结如下:有两个账户M,N。且M&amp;gt;N。设从账户M转出Y元,则以下等式成立:
Y0.940.95+N=M-Y (依据是:最终账户里的钱数相等)
化简得:M-N=1.893Y
0.893Y是所花的费用。费用最小,则由上式知M-N最小。

回归到原题目:将23个账户按照从大到小排序,找到X的下标m,使得:
(X1+X2+……Xm)-(X(m+1)+X(m+2)……X22+X23)最小

则所花费用为((X1+X2+……Xm)-(X(m+1)+X(m+2)……X22+X23))/1.893*0.893
(账目总额—所花费用)/23 为最终每个账户的钱数

若M=N情况较为简单就不再罗嗦!