[プログラム設計実習]大整数の四則演算
6904 ワード
説明
2つの正の整数と4つの演算オペレータ(+-*/)を与え、演算結果を求める.
1行目:正の整数a、長さが100を超えない2行目:4則演算子o、oは「+」、「-」、「*」、「/」のいずれかの3行目:正の整数b、長さが100を超えない
入力に余分なスペースや他の文字が含まれていないことを保証します.式「a o b」の値を出力します.
補足説明:1.減算結果は負数2になる可能性がある.除算結果を下に修正する.出力は日常の書く習慣に合っており、余分な0、スペース、その他の文字は使用できません.
もともと授業中はC++で書いていたのですが、うっかりなくしてしまい、ちょうどOJにもこの問題のバックアップがなく、ついでにJavaで1つ書きました.
C++で書くのはとても便利ですね.直接クラスを作って演算子を再ロードすればいいです.Javaはツールクラスと静的な方法を書くしかありません.考えてみるとつらいです.
以下はアイデアを提供するだけで、パクリしないで宿題を提出して、ツッコミの効率/文法/細部を批判することを歓迎します(OJはC++だけを支持して、私もこれが过ごすことができるかどうか分かりません!).
各数字は最高100ビットに達するため、直接演算は効率が低いだけでなく、精度の損失も発生する可能性があるため、数字を変換した文字列を珠算方法でビットで計算し、コードは以下の通りである.
2つの正の整数と4つの演算オペレータ(+-*/)を与え、演算結果を求める.
1行目:正の整数a、長さが100を超えない2行目:4則演算子o、oは「+」、「-」、「*」、「/」のいずれかの3行目:正の整数b、長さが100を超えない
入力に余分なスペースや他の文字が含まれていないことを保証します.式「a o b」の値を出力します.
補足説明:1.減算結果は負数2になる可能性がある.除算結果を下に修正する.出力は日常の書く習慣に合っており、余分な0、スペース、その他の文字は使用できません.
もともと授業中はC++で書いていたのですが、うっかりなくしてしまい、ちょうどOJにもこの問題のバックアップがなく、ついでにJavaで1つ書きました.
C++で書くのはとても便利ですね.直接クラスを作って演算子を再ロードすればいいです.Javaはツールクラスと静的な方法を書くしかありません.考えてみるとつらいです.
以下はアイデアを提供するだけで、パクリしないで宿題を提出して、ツッコミの効率/文法/細部を批判することを歓迎します(OJはC++だけを支持して、私もこれが过ごすことができるかどうか分かりません!).
各数字は最高100ビットに達するため、直接演算は効率が低いだけでなく、精度の損失も発生する可能性があるため、数字を変換した文字列を珠算方法でビットで計算し、コードは以下の通りである.
public class BigNumber {
/**
*
*/
private static int compare(String a, String b) {
if (a.length() != b.length()) {
//
return a.length() - b.length();
} else {
for (int i = 0; i < a.length(); i++) {
// ASCII
if (a.charAt(i) != b.charAt(i)) {
return a.charAt(i) - b.charAt(i);
}
}
// 0
return 0;
}
}
/**
*
*/
private static String opposite(String a) {
// ,
if (a.charAt(0) == '-') {
return a.substring(1);
} else {
return "-" + a;
}
}
/**
*
*/
public static String add(String a, String b) {
//
if (a.charAt(0) == '-' && b.charAt(0) == '-') {
return opposite(add(a.substring(1), b.substring(1)));
} else if (a.charAt(0) == '-') {
return subtract(b, a.substring(1));
} else if (b.charAt(0) == '-') {
return subtract(a, b.substring(1));
} else {
String result = "";
// 0
while (a.length() < b.length()) {
a = "0" + a;
}
while (a.length() > b.length()) {
b = "0" + b;
}
//
int carry = 0;
//
for (int i = a.length() - 1; i >= 0; i--) {
int num = (a.charAt(i) - 48) + (b.charAt(i) - 48) + carry;
if (num >= 10) {
num -= 10;
carry = 1;
} else {
carry = 0;
}
result = num + result;
}
if (carry == 1) {
return 1 + result;
}
return result;
}
}
/**
*
*/
public static String subtract(String a, String b) {
//
if (a.charAt(0) == '-' && b.charAt(0) == '-') {
return opposite(subtract(a.substring(1), b.substring(1)));
} else if (a.charAt(0) == '-') {
return opposite(add(a.substring(1), b));
} else if (b.charAt(0) == '-') {
return add(a, b.substring(1));
} else if (compare(a, b) < 0) {
return opposite(subtract(b, a));
} else if (compare(a, b) == 0) {
return "0";
} else {
String result = "";
// 0
while (a.length() < b.length()) {
a = "0" + a;
}
while (a.length() > b.length()) {
b = "0" + b;
}
//
int carry = 0;
//
for (int i = a.length() - 1; i >= 0; i--) {
int num = (a.charAt(i) - 48) - (b.charAt(i) - 48) - carry;
if (num < 0) {
num += 10;
carry = 1;
} else {
carry = 0;
}
result = num + result;
}
if (result.charAt(0) == '0') {
return result.substring(1);
}
return result;
}
}
/**
*
*/
public static String multiply(String a, String b) {
// 0
if ("".equals(b.replaceAll("0", "")) || "".equals(b.replaceAll("0", ""))) {
return "0";
} else if (a.charAt(0) == '-' && b.charAt(0) == '-') {
return multiply(a.substring(1), b.substring(1));
} else if (a.charAt(0) == '-') {
return opposite(multiply(a.substring(1), b));
} else if (b.charAt(0) == '-') {
return opposite(multiply(a, b.substring(1)));
} else {
// add
String result = "";
String inner;
int num;
for (int i = 0; i < b.length(); i++) {
num = b.charAt(i) - 48;
inner = "0";
while (num-- > 0) {
inner = add(inner, a);
}
result = add(result + 0, inner);
}
return result;
}
}
/**
*
*/
public static String divide(String a, String b) {
// 0
if ("".equals(b.replaceAll("0", ""))) {
throw new RuntimeException(" 0");
} else if (a.charAt(0) == '-' && b.charAt(0) == '-') {
return divide(a.substring(1), b.substring(1));
} else if (a.charAt(0) == '-') {
return opposite(divide(a.substring(1), b));
} else if (b.charAt(0) == '-') {
return opposite(divide(a, b.substring(1)));
} else if (compare(a, b) < 0) {
return "0";
} else if (compare(a, b) == 0) {
return "1";
} else {
// subtract
String result = "";
int num;
int len = b.length();
while (a.length() > b.length()) {
b += "0";
}
while (b.length() >= len) {
num = 0;
while (compare(a, b) >= 0) {
num++;
a = subtract(a, b);
}
result = result + num;
b = b.substring(0, b.length() - 1);
}
if (result.charAt(0) == '0') {
return result.substring(1);
}
return result;
}
}
}