总共有n枚硬币，将它们摆成一个阶梯形状，第k行必须正好要有k枚硬币。给定一个数字n，给出可形成完整阶梯行的总行数（若当行凑不了，就返回上一行）
首先，我们最容易想到的思路就是，用一个for循环，每次这个n减去循环变量i,然后判断是否小于i.因为要排列成阶梯的话，他必须是第k行有k个数。所以这样就可以了。
1 private static int violentArrangeCoins(int x){ 2 for(int i = 1;i <= x;++i){ 3 x = x - i; 4 if(x <= i){ 5 return i; 6 } 7 } 8 return 0; 9 }
现在我们仔细分析一下这个过程，其实还可以用二分查找来做。我们定义low=0,high=n,那么就可以算出一个mid.然后，根据等差数列求和，我们可以算出从1到mid的和。我们把这个和记作cost.现在我们就拿这个cost和n进行比较.如果正好等于n,那么就OK，恭喜，我们一次就找到了行数，直接返回mid即可。否则，按照二分查找的那样来处理。具体看看代码：
1 public static int arrangeCoins(int n){ 2 int low = 0, high = n; 3 while(low <= high) 4 { 5 int mid = (high - low) / 2 + low; 6 int cost = (mid * (mid+1)) / 2; 7 if(cost == n){ 8 return mid; 9 }else if(cost < n){ 10 low = mid + 1; 11 }else{ 12 high = mid - 1; 13 } 14 } 15 return low; 16 }
我们再来仔细分析一下这个过程：等差数列求和这一部分，mid2+mid=2*cost这里，其实mid就等于2倍cost减去mid再开方。那么这里就相当于是牛顿迭代。所以，受到启发，我们还可以用牛顿迭代来处理这个问题。
1 public static int arrangeInNewton(int n){ //使用牛顿迭代 2 if(n == 0){ 3 return 0; 4 } 5 return (int)sqrt(n,n); 6 } 7 8 private static double sqrt(double x, int n){ //这里就是牛顿迭代里的核心:求平方根 9 double res = (x + (2*n-x) / x) / 2; 10 if(res == x){ 11 return x; 12 }else{ 13 return sqrt(res, n); 14 } 15 }
以上三种方法的测试效果如下：
（忘记了一件重要的事
完整代码如下：
1 package com.hw.list0710; 2 3 import java.util.Scanner; 4 5 public class ArrangeCoins { 6 public static int arrangeCoins(int n){ 7 int low = 0, high = n; 8 while(low <= high) 9 { 10 int mid = (high - low) / 2 + low; 11 int cost = (mid * (mid+1)) / 2; 12 if(cost == n){ 13 return mid; 14 }else if(cost < n){ 15 low = mid + 1; 16 }else{ 17 high = mid - 1; 18 } 19 } 20 return low; 21 } 22 23 public static int arrangeInNewton(int n){ //使用牛顿迭代 24 if(n == 0){ 25 return 0; 26 } 27 return (int)sqrt(n,n); 28 } 29 30 private static double sqrt(double x, int n){ //这里就是牛顿迭代里的核心:求平方根 31 double res = (x + (2*n-x) / x) / 2; 32 if(res == x){ 33 return x; 34 }else{ 35 return sqrt(res, n); 36 } 37 } 38 39 private static int violentArrangeCoins(int x){ 40 for(int i = 1;i <= x;++i){ 41 x = x - i; 42 if(x <= i){ 43 return i; 44 } 45 } 46 return 0; 47 } 48 49 public static void main(String[] args) { 50 System.out.println("输入一个数:"); 51 Scanner s = new Scanner(System.in); 52 int n = s.nextInt(); 53 s.close(); 54 int re = violentArrangeCoins(n); 55 int res = arrangeCoins(n); 56 int result = arrangeInNewton(n); 57 System.out.println("使用暴力法:"+re); 58 System.out.println("使用二分查找法:"+res); 59 System.out.println("使用牛顿迭代法:"+result); 60 } 61 }