一个简单的题目，看看大家有没有好的算法

long类型太小，使用Java大数
public static void main(String[] args){
  BigInteger sum = new BigInteger("11111111111111111111111111111111111");
  String s = "8";
  while(s.length()<=20){
    sum = sum.add(new BigInteger(s));
    s+="8";
  }
  sum = sum.subtract(new BigInteger("11111111111111111111111111111111111"));
  System.out.println(sum);
}

        public static void main(String[] args) {
             int sum=0,number=0;
for(int i=0;i<2;i++){
    number=number*10+8;
sum=number+sum;
}
System.out.println("和为:"+sum);
}
     很笨的方法·············

public static void main(String[] args) {
int sum=0,number=0;
for(int i=0;i<20;i++){
number=number*10+8;
sum=number+sum;
}
System.out.println("和为:"+sum);
}刚才搞错应该是20呵呵

楼上的zxliujun如果稍微懂点Java基础知识就不会犯那么低级的错误了！
要求前20位的和，怎么可能能用int型数据来接收呢，肯定是用大整形数BigInteger来接收的吗，下面的我就不说了……

public class Test {
/*
* 8+88+888 = 8*(3-0)*(10^0)+8*(3-1)*(10^1)+8*(3-2)*(10^2)
* 8+88+888+8888 = 8*(4-0)*(10^0)+8*(4-1)*(10^1)+8*(4-2)*(10^2)+8*(4-3)*(10^3)
*/
    public static void main(String[] args) throws Exception {
     System.out.print(method1(8,20));
    }

    public static BigInteger method1(int arg1, int arg2){
     BigInteger b = new BigInteger(String.valueOf(arg1));
     BigInteger t = new BigInteger("10");
     BigInteger r = new BigInteger("0");
     for (int i = 0; i < arg2; i++){
     r = r.add(
     b.multiply(new BigInteger(String.valueOf(arg2 - i)))
     .multiply(t.pow(i)));
     }
     return r;
    }
}

应该是
一个简单的题目，看大家有没有最好的算法来求解。
题目为：求8+88+888+....前N项之和，用java编写。可以转化成N个8，N-1个80.....，1个8*10^（N-1）之和，用大数计算

long sum = 0;
StringBuffer s = new StringBuffer(8) ;
for(int i=0;i<20;i++){
for(int j=0;j<i;j++){
s.append(s);
}
long s1=Long.parseLong(s.toString());
sum+=s1;
}
System.out.println(sum);没有执行过，我1.4版本的jdk执行不了。
大概可以用吧。

    /**
     * p+pp+ppp+pppp的前top项和
     * @param top 前N项
     * @param p 每项的权
     * @return
     */
    public static BigInteger getSumTops(BigInteger top, BigInteger p) {
        BigInteger sum = BigInteger.ONE;
        BigInteger pow = new BigInteger("10");//左移用
        for (BigInteger i = new BigInteger("2"); top.compareTo(i) >= 0; i = i.add(BigInteger.ONE)) {
            sum = sum.multiply(pow).add(i);
        }
        return sum;
    }    public static void main(String[] args) {
        System.out.println(getSumTops(new BigInteger("6"), new BigInteger("8")));

        //查验结果
        int s = 0;
        int p = 8;
        for (int i = 1; i <= 6; i++) {
            s += p;
            p = p * 10 + 8;
        }
        System.out.println(s);
    }

理解的方式不同，结果是一样的
这是发现的一个规律
前N项和    结果
1          1
2          12
3          123
.................
8          12345678
9          123456789
10         1234567890+10
11         12345679000+11
将N-1项的结果左移一位再加项号N就是前N项和
a1=1
an=a(n-1)*10+n

令             Sn=8+88+888+...+8...88
有          10*Sn=  80+880+...+8...80+8...880
有 8*(n+1)+10*Sn=8+88+888+...+8...88+8...888
3-1得：
   8*(n+1)+9*Sn=8...888(n+1个8)
故             Sn=(8...888-8*(n+1))/9
import java.math.BigInteger;
public class Test{
public static void main(String args[]) {
    int n=20;
    String s="";
    for(int i=1;i<=n+1;i++){
     s+='8';
    }
    BigInteger bi[]={new BigInteger(s),new BigInteger(""+9),new BigInteger(""+(8*(n+1)))};
    BigInteger i=(bi[0].subtract(bi[2])).divide(bi[1]);
    System.out.println(i);
}
}

两个思路
第一种前面有人说过了，这里再大概描述下
算式最后可以表示为n*8+(n-1)*8*10^1+...+1*8*10^(n-1)
这个计算就简单了，一个for循环搞定，如下： public String compute(int n) {
BigInteger bi = BigInteger.ZERO;
for (int i=n;i>0;i--) {
int j = 8;
BigInteger b = BigInteger.valueOf(j).multiply(BigInteger.TEN.pow(i-1)).multiply(BigInteger.valueOf(n-i+1));
bi = bi.add(b);
}

return bi.toString();
}

第二种思路思考起来简单些，就是先用数学公式求数列的和
就LZ给出的数列，第n项为8+8*10+...+8*10^(n-1)
这是一个等比数列，可以得出，第n项的通项式为8*(10^n-1)/9
所以LZ的数列和可以表示为
8*(10-1)/9+...+8*(10^n-1)/9=8*((10+...+10^n)-n)/9=8*((10^(n+1)-10)/9-n)/9
求最后这个算式当n=20时的值就可以了
附一个我写的求简单算式值的代码：import java.math.BigDecimal;
import java.math.MathContext;
import java.util.LinkedList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class TestCalculate {
private LinkedList<IComp> stack = new LinkedList<IComp>();
private String regex="(\\(|\\)|\\+|\\-|\\*|\\/|\\^|\\d+(\\.\\d+)?)";
private MathContext mc = new MathContext(30);

public String compute(String str) {
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(str);

IComp ol=null;
BigDecimal fn=BigDecimal.ZERO, sn=null;

while (m.find()) {
String s = m.group();
if (s.equals(")")) {
fn = compute(fn, sn, ol.getSymbol());
ol = null;
sn = null;
for (IComp t = stack.pop();t.getLevel()!=0;t=stack.pop()) {
if (t.isNumber()) {
sn = fn;
fn = ((NumberComp)t).getValue();
fn = compute(fn, sn, ol.getSymbol());
ol = null;
sn = null;
}
else {
ol = t;
}
}

if (stack.peekFirst()!=null&&stack.peekFirst().getLevel()!=0) {
sn = fn;
ol = stack.pop();
fn = ((NumberComp)stack.pop()).getValue();
}
}
else {
IComp c = CompFactory.createComp(s);

if (c.isNumber()) {
if (ol==null) {
fn = ((NumberComp)c).getValue();
}
else {
sn = ((NumberComp)c).getValue();
}
}
else {
int l = c.getLevel(); if (l==0) {
if (ol!=null) {
stack.push(new NumberComp(fn));
stack.push(ol);
}
stack.push(c);
fn = BigDecimal.ZERO;
ol = null;
}
else {
if (ol!=null) {
if (ol.getLevel()>=l) {
fn = compute(fn, sn, ol.getSymbol());
ol = c;
}
else {
stack.push(new NumberComp(fn));
stack.push(ol);
fn = sn;
ol = c;
}
sn = null;
}
else {
ol = c;
}
}
}
}
}

if (ol!=null) {
fn = compute(fn, sn, ol.getSymbol());
ol = null;
sn = null;
}

for (IComp t = stack.peekFirst();t!=null;t=stack.peekFirst()) {
if (t.isNumber()) {
sn = fn;
fn = ((NumberComp)t).getValue();
fn = compute(fn, sn, ol.getSymbol());
ol = null;
sn = null;
}
else {
ol = t;
}

stack.pop();
} return fn.toEngineeringString();
}

private BigDecimal compute(BigDecimal first, BigDecimal second, String symbol) {
if ("+".equals(symbol)) {
return first.add(second, mc);
}
else if ("-".equals(symbol)) {
return first.subtract(second, mc);
}
else if ("*".equals(symbol)) {
return first.multiply(second, mc);
}
else if ("/".equals(symbol)) {
return first.divide(second, mc);
}
else if ("^".equals(symbol)) {
return first.pow(second.intValue(), mc);
}
else {
return null;
}
}

public static void main(String[] args) {
String s = "8*((10^(n+1)-10)/9-n)/9";
String n = "20";

TestCalculate test = new TestCalculate();
System.out.print(s.replaceAll("n", n));
System.out.print("=");
System.out.println(test.compute(s.replaceAll("n", n)));
}
}interface IComp {
boolean isNumber();
String getSymbol();
int getLevel();
}class NumberComp implements IComp {
private BigDecimal val;

public NumberComp(String s) {
val = new BigDecimal(s);
}

public NumberComp(BigDecimal b) {
val = b;
}

public BigDecimal getValue() {
return val;
}

@Override
public String getSymbol() {
return val.setScale(2).toString();
}

@Override
public int getLevel() {
return -1;
}

@Override
public boolean isNumber() {
return true;
}

@Override
public String toString() {
return getSymbol();
}
}class AddComp implements IComp {
@Override
public int getLevel() {
// TODO Auto-generated method stub
return 1;
}

public String getSymbol() {
return "+";
}

@Override
public boolean isNumber() {
// TODO Auto-generated method stub
return false;
}
}class SubComp implements IComp {
@Override
public int getLevel() {
// TODO Auto-generated method stub
return 1;
}

public String getSymbol() {
return "-";
}

@Override
public boolean isNumber() {
// TODO Auto-generated method stub
return false;
}
}class MultComp implements IComp {
@Override
public int getLevel() {
return 2;
}

public String getSymbol() {
return "*";
}

@Override
public boolean isNumber() {
// TODO Auto-generated method stub
return false;
}
}class DivComp implements IComp {
@Override
public int getLevel() {
return 2;
}

public String getSymbol() {
return "/";
}

@Override
public boolean isNumber() {
// TODO Auto-generated method stub
return false;
}
}class PowComp implements IComp {
@Override
public int getLevel() {
return 3;
}

public String getSymbol() {
return "^";
}

@Override
public boolean isNumber() {
// TODO Auto-generated method stub
return false;
}
}class SymbolComp implements IComp {
@Override
public int getLevel() {
return 0;
}

public String getSymbol() {
return "(";
}

@Override
public boolean isNumber() {
return false;
}
}class CompFactory {
private static AddComp add = new AddComp();
private static SubComp sub = new SubComp();
private static MultComp mult = new MultComp();
private static DivComp div = new DivComp();
private static PowComp pow = new PowComp();
private static SymbolComp sb = new SymbolComp();

public static IComp createComp(String s) {
if (s.matches("\\d+(\\.\\d+)?")) {
return new NumberComp(s);
}
else if (add.getSymbol().equals(s)) {
return add;
}
else if (sub.getSymbol().equals(s)) {
return sub;
}
else if (mult.getSymbol().equals(s)) {
return mult;
}
else if (div.getSymbol().equals(s)) {
return div;
}
else if (pow.getSymbol().equals(s)) {
return pow;
}
else if (sb.getSymbol().equals(s)) {
return sb;
}
else {
return null;
}
}
}

说明下，上面的类只是刚好前两天我闲的蛋疼写着玩的，今天刚好可以拿来用，呵呵
实际上求那个等式不用那么复杂，用下面的两行代码一下就出来了 int n=20;
System.out.println(BigInteger.valueOf(8).multiply((BigInteger.TEN.pow(n+1).subtract(BigInteger.TEN)).divide(BigInteger.valueOf(9)).subtract(BigInteger.valueOf(n)).divide(BigInteger.valueOf(9))));

public class T { /**
* @param args
*/
public static void main(String[] args) {
int n = 20000;
System.out.println(n);
long t1 = (new Date()).getTime();
T.method1(n);
long t2 = (new Date()).getTime();
System.out.println(t2 - t1);

t1 = (new Date()).getTime();
T.method2(n);
t2 = (new Date()).getTime();
System.out.println(t2 - t1);
} /**
* 令 Sn=8+88+888+...+8...88 有 10*Sn= 80+880+...+8...80+8...880 有
* 8*(n+1)+10*Sn=8+88+888+...+8...88+8...888 3-1得：
* 8*(n+1)+9*Sn=8...888(n+1个8)
*
* 故 Sn=(8...888-8*(n+1))/9
* @param n
* @return
*/
public static BigInteger method1(int n) {
String s = "";
for (int i = 1; i <= n + 1; i++) {
s += '8';
}
BigInteger bi[] = { new BigInteger(s), new BigInteger("" + 9),
new BigInteger("" + (8 * (n + 1))) };
BigInteger i = (bi[0].subtract(bi[2])).divide(bi[1]);
return i;
}

/**
*
* @param n
* @return
*/
public static BigInteger method2(int n) {
StringBuffer s = new StringBuffer();
for (int i = 1; i <= n + 1; i++) {
s.append('8');
}
BigInteger bi[] = { new BigInteger(s.toString()), new BigInteger("9"),
new BigInteger("" + (8 * (n + 1))) };
BigInteger i = (bi[0].subtract(bi[2])).divide(bi[1]);
return i;
}
}
/**
*测试结果：20000
484
63
用19楼毫秒
*/

public static void main(String[] args) {
int a = 8;
int n = 20;
long sum = 0;
String s = "";
ArrayList<String> arr = new ArrayList<String>();
for (int x = 0; x < n; x++) {
s += ("" + a);
arr.add(s);
}
for(String ss: arr){
sum+=Long.parseLong(ss);
}
System.out.println(sum);
}

调试易

一个简单的题目，看看大家有没有好的算法

解决方案 »