首页 > 专题系列 > Java解POJ > POJ 2562 Primary Arithmetic [解题报告] Java
2013
11-11

POJ 2562 Primary Arithmetic [解题报告] Java

Primary Arithmetic

问题描述 :

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the “carry” operation – in which a 1 is carried from one digit position to be added to the next – to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.

输入:

Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.

输出:

For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.

样例输入:

123 456
555 555
123 594
0 0

样例输出:

No carry operation.
3 carry operations.
1 carry operation.

解题代码:

//* @author 洪晓鹏<hongxp11@163.com>
import java.util.Scanner;


public class Main {
 public static void main(String[] args)
  {
  Scanner in = new Scanner(System.in);
   while(true)
    {
	String first = in.next();
	String second = in.next();
	//System.out.println(first.length()+" "+second.length());
	if(first.equals("0") && second.equals("0"))
	{
		break;
	}
	int carry = 0;
	int result = 0;
	int n = first.length();
	int k = 0;
	if(first.length() > second.length())
	{
		n = first.length();
		k = first.length() - second.length();
		for(int i = 0; i < k; i++)
			second = '0'+second;
	}
	else if(first.length() < second.length())
	{
		n = second.length();
		k = second.length() - first.length();
		for(int i = 0; i < k; i++)
			first = '0'+first;
	}
		
			
	//System.out.println("first:"+first+"second:"+second+"n:"+n+"k"+k);
	for(int i = n-1; i>=0; i--)
	{
		int m = (first.charAt(i)-'0')+(second.charAt(i) -'0')+carry;
		if(m>9)
		{
			result++;
			carry = 1;
		}
		else
			carry =0;
	}

			
	//输出处理
    if( result == 0)
    {
    	System.out.println("No carry operation.");
    }
    else if(result == 1)
    {
    	System.out.println("1 carry operation.");
    }
    else
    {
    	System.out.println(result + " carry operations.");
    }	
  }
 }
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测