首页 > 试题广场 >

小球的距离

[编程题]小球的距离

热度指数：13331 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小东和三个朋友一起在楼上抛小球，他们站在楼房的不同层，假设小东站的楼层距离地面N米，球从他手里自由落下，每次落地后反跳回上次下落高度的一半，并以此类推直到全部落到地面不跳，求4个小球一共经过了多少米？(数字都为整数)

给定四个整数A,B,C,D，请返回所求结果。

测试样例：

100,90,80,70

返回：1020

算法知识视频讲解

YEN-NEUer

/**
*算整数的时候由于int会忽略小数点后的 比如：从9落下来，9/2=4，在上升4 就是8，而真是情况是下来后4.5+上升4.5=9 所以如果奇数会算少了，要向上取整，偶数正确
*/ public int calcDistance(int A, int B, int C, int D) {
         //write code here
        int dis=A+B+C+D; //每个球第一次下落的高度
        while ( A>0 || B >0 || C>0 || D>0 ){
            if(A>0){
                if(A%2==0) dis+=A;
                else dis+=((A+1)/2)*2;
                A/=2;
            }
            if(B>0){
                if(B%2==0) dis+=B;
                else dis+=((B+1)/2)*2;
                B/=2;
            }
            if(C>0){
                if(C%2==0) dis+=C;
                else dis+=((C+1)/2)*2;
                C/=2;
            }
            if(D>0){
                if(D%2==0) dis+=D;
                else dis+=((D+1)/2)*2;
                D/=2;
            }

        }
        return dis;
    } }

编辑于 2016-10-11 14:38:37 回复(0)

更多回答

大大的逗比


	没有数学分析到可以用极限，但是递归还是解决问题了 



	public int calcDistance(int A, int B, int C, int D) {
		double len=0;
		len+=getLen(A*1.0,0);
		len+=getLen(B*1.0,0);
		len+=getLen(C*1.0,0);
		len+=getLen(D*1.0,0);
		return (int) Math.round(len);
    }
	private double getLen(double a,double sum) {
        if (a<=0) {
			return  sum;
		}
        sum+=a+a/2;
		return getLen(a/2, sum);	
	}

编辑于 2016-08-11 14:36:21 回复(3)

drdr

class Balls {
public:
    int calcDistance(int A, int B, int C, int D) {
        // write code here
		return 3*(A + B + C + D);
    }
};

发表于 2017-04-19 15:01:39 回复(1)

J2eremy

class Balls {
public:
    double count(double X){
        double sum = X;
        while(X > 0){
            X = X / 2;
            sum += 2*X;
        }
        return sum;
    }
    int calcDistance(int A, int B, int C, int D) {
        double sum = count(A)+count(B)+count(C)+count(D);
        return ceil(sum);
    }
};

发表于 2017-06-07 17:56:38 回复(0)

辛劳小码农

public int calcDistance(int A, int B, int C, int D) {

// write code here

return (A+B+C+D)*3;

}

这是我做过最简单的一个了

发表于 2016-08-30 17:21:43 回复(1)

0↓1du

def countway(a, b, c, d):
    return 3*(a+b+c+d)

发表于 2018-04-09 17:09:51 回复(0)

C/C++

nbgao

class Balls {
public:
    int calcDistance(int A, int B, int C, int D) {
        return 3*(A+B+C+D);
    }
};

发表于 2017-10-13 00:50:47 回复(0)

nineteen.

这题和前面的京东《抛小球》问题重复了，不解释

发表于 2017-09-08 15:48:28 回复(0)

wangwenbin

// 数学题，求极限
import java.util.*;

public class Balls {
    public int calcDistance(int A, int B, int C, int D) {
        // write code here
        return 3*(A+B+C+D);
    }
}

发表于 2017-09-07 10:59:07 回复(0)

Forrestcloud

ceil() 向上取整，向无穷大舍入；

class Balls {

public:

//利用极限的思想；x+1/2*x*2+1/4*x*2+1/8*x*2.......==3*x

//普通思路

int calcDistance(int A, int B, int C, int D) {

// write code here

//极限思路

//return 3*(A+B+C+D);

//普通思路

double x = A+B+C+D,sum = x;

while(x > 0){

sum += x;

x /= 2.0;

}

return ceil(sum);

}

};

发表于 2017-09-06 21:38:44 回复(0)

H掠影

咱也是上过小学的人

class Balls {

public:

int calcDistance(int A, int B, int C, int D) {

// write code here

return 3*(A+B+C+D);

}

};

发表于 2017-03-31 21:46:25 回复(0)

冷色探戈

	/**
	 * 迭代
	 * @param A
	 * @param B
	 * @param C
	 * @param D
	 * @return
	 */
	public int calcDistance(int A, int B, int C, int D) {
		return (int)Math.round(countDis(A*1.0)+countDis(B*1.0)+countDis(C*1.0)+countDis(D*1.0));
	}

	/**
	 *
	 * @param a
	 * @return
	 */
	private double countDis(double a) {
		double dis = a;
		while (a > 0) {
			a /= 2.0;
			dis += 2*a;
		}
		return dis;
	}

发表于 2017-03-31 19:40:36 回复(0)

Scheaven

/*
 *@算法思路：等比数列，有人问数学不好怎么办，像这种题完全可以忽略计算过程，
 *因为q<1;极限就是 return (1/q+1)sum;
*/
    public int calcDistance(int A, int B, int C, int D) {
        return 3*(A+B+C+D);
    }

编辑于 2016-08-13 17:44:24 回复(0)

ent9

int calcDistance(int A, int B, int C, int D) 
{
    // write code here
    int res = 0;
    while(A)
    {
        res += A;
        A /= 2;
        res += A;
    }

    while(B)
    {
        res += B;
        B /= 2;
        res += B;
    }

    while(C)
    {
        res += C;
        C /= 2;
        res += C;
    }

    while(D)
    {
        res += D;
        D /= 2;
        res += D;
 	}

    return res;
}

请问这段代码哪里有问题吗？ 我输出的是996 好像不对啊 思路哪里错了吗？


改成了
    double res = 0;
    double a = A;
    double b = B;
    double c = C;
    double d = D;

    while(a)
    {
        res += a;
        a /= 2;
        res += a;
    }
 
    while(b)
    {
        res += b;
        b /= 2;
        res += b;
    }
 
    while(c)
    {
        res += c;
        c /= 2;
        res += c;
    }
 
    while(d)
    {
        res += d;
        d /= 2;
        res += d;
    }

    return res + 0.5;

就通过了...

编辑于 2016-07-29 16:32:05 回复(6)

吐蕃国师大轮明王鸠摩智

// 画图可知，假设开始时距地面N米，这N米的过程只经过1次，接下来的过程是弹起来N/2再
// 落下N/2，弹起来N/4再落下N/4...因此，总的路程S=N+2N(1/2+1/4+1/8+...)=N+N(1+1/2+1/4+1/8+...)。由等比数列的求和公式,当数列长度趋于无穷时，S=3N。 
import java.util.*;

public class Balls {
    public int calcDistance(int A, int B, int C, int D) {
        // write code here
        return 3*(A+B+C+D);
    }
}

编辑于 2016-04-01 11:04:45 回复(0)

小小

class Balls {
public:
    int calcDistance(int A, int B, int C, int D) {
		int ret = A + B + C + D;
		return ret * 3;
    }
};

发表于 2015-10-29 10:19:28 回复(0)

我就是你想要的Offer

刚开始做这个题受到了括号里数字都为整数的误导，以为落地距离是5米，弹起后2米（5/2自动取整）。算出来结果不对，变小了。所以，不是自动取整。就是所有的都算进去，这就牵扯到数学上的极限思想了。除了最开始的下落高度只加一次外，以后的弹起下落都是两倍的距离。举个例子，下落高度是x米，则有下落后弹起的高度是x/2，再落下去，又走了一个x/2，依此类推，一直下去，也就是总距离为 x+2*x（1/2+1/4+1/8+……），而括号中的数列是一个等比数列，其极限求和的结果就是1。所以总距离就是3*x。推理到这里，就发现写程序只需要一行关键代码就可以。


	classBalls {



	public:



	intcalcDistance(intA, intB, intC, intD) {



	// write code here



	return 3*(A+B+C+D);



	}



	};

编辑于 2019-08-26 15:58:03 回复(22)

cycleof

class Balls {
public:
    int calcDistance(int A, int B, int C, int D) {
        double x = A+B+C+D,sum = x;//普通思路
        while(x > 0){
            sum += x;
            x /= 2.0;
        }
        return ceil(sum);
        /*return ( 3*(A+B+C+D) );*/ //极限思想
    }
};

发表于 2017-07-26 18:11:18 回复(0)

Java

放学后我不走~

传说中的一行代码：

return 3*(A+B+C+D);

分析：数学计算

代码如下：

import java.util.*;
public class Balls {
public int calcDistance(int A, int B, int C, int D) {
// write code here
return 3*(A+B+C+D);//实际就这一行代码
}
}

发表于 2018-08-19 17:53:41 回复(0)

贪I狼

按照小东的 100 米进行分析，每次反弹米数为 D(n), 每次反弹小球经过米数为 F(n)

1.第 0 次反弹：即不扔球时，F(0) = 0, D(0) = 0

2.第 1 次反弹：即扔球，D(1) = 50, F(1) = 100 + D(1) = 150

3.第 2 次反弹：D(2) = 25, F(2) = F(1) + D(1) + D(2) = 225

4.第 3 次反弹：D(3) = 12.5, F(3) = F(2) + D(2) + D(3) = 262.5

5.依次类推，可知 F(n) = F(n - 1) + D(n - 1) + D(n)

所以，可以先计算出小球初试位置到落地时的所有值，然后按递推计算，最终得到如下代码：

import java.util.ArrayList;
import java.util.List;

public class Main {

	public static int calcDistance(int A, int B, int C, int D) {
		return ballDistance(A) + ballDistance(B) + ballDistance(C) + ballDistance(D);
	}
	
	// 计算每个小球会经过多少米
	public static int ballDistance (int N) {
		// 每次反弹多少米
		List<Double> disList = new ArrayList<Double>();
		disList.add(0.0);									// 第 0 次，没扔球，不反弹
		double n = N;
		while (n != 0) {
			n = n / 2.0;
			disList.add(n);
		}
		
		// 反弹的次数 
		int count = disList.size();
		double[] rs = new double[count];
		rs[0] = N;
		for (int i = 1; i < count; i ++) {
			rs[i] = rs[i - 1] + disList.get(i) + disList.get(i - 1);
		}
		
		int distance = (int) Math.round(rs[count - 1]);
		return distance;
	}

	public static void main(String[] args) {
		int rs = calcDistance(100, 90, 80, 70);
		System.out.println(rs);
	}

}

其实，输入 100，打印数组 rs，可以看到其值为 [100.0, 150.0, 225.0, 262.5, 281.25, 290.625, 295.3125, 297.65625, 298.828125, 299.4140625, 299.70703125, 299.853515625, 299.9267578125, ....， 300， ...， 300]，最终恒定为 300，即 100 * 3

发表于 2017-04-07 14:17:50 回复(0)