算法题（求两个大数的差）

本文概述

C++
Java
Python3
C#
PHP
C++
Java
Python3
C#
PHP

给定两个数字作为字符串。这些数字可能非常大(可能不适合int long int int), 任务是找到这两个数字的差。
例子：

Input : str1 = "11443333311111111100", str2 ="1144422222221111" Output : 11442188888888889989Input :str1 = "122387876566565674", str2 ="31435454654554" Output : 122356441111911120

这是基于学校数学的简单方法。我们从头开始遍历两个字符串, 一个接一个的减数位。

颠倒两个字符串。
继续从第0个索引开始(以反向字符串)一一减一到小字符串的末尾, 如果对结果的末尾是正数, 则追加差异。如果difference(diff)为负, 则加10, 如果正值为正, 则将进位保持为1, 则进位为0。
最后, 反转结果。

以下是上述想法的实现：
C++

//C++ program to find difference of two large numbers. #include < bits/stdc++.h> using namespace std; //Returns true if str1 is smaller than str2. bool isSmaller(string str1, string str2) { //Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); if (n1 < n2) return true ; if (n2 < n1) return false ; for ( int i = 0; i < n1; i++) if (str1[i] < str2[i]) return true ; else if (str1[i]> str2[i]) return false ; return false ; } //Function for find difference of larger numbers string findDiff(string str1, string str2) { //Before proceeding further, make sure str1 //is not smaller if (isSmaller(str1, str2)) swap(str1, str2); //Take an empty string for storing result string str = "" ; //Calculate length of both string int n1 = str1.length(), n2 = str2.length(); //Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; //Run loop till small string length //and subtract digit of str1 to str2 for ( int i = 0; i < n2; i++) { //Do school mathematics, compute difference of //current digits int sub = ((str1[i] - '0' ) - (str2[i] - '0' ) - carry); //If subtraction is less then zero //we add then we add 10 into sub and //take carry as 1 for calculating next step if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str.push_back(sub + '0' ); } //subtract remaining digits of larger number for ( int i = n2; i < n1; i++) { int sub = ((str1[i] - '0' ) - carry); //if the sub value is -ve, then make it positive if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str.push_back(sub + '0' ); } //reverse resultant string reverse(str.begin(), str.end()); return str; } //Driver code int main() { string str1 = "978" ; string str2 = "12977" ; //Function call cout < < findDiff(str1, str2) < < endl; string s1 = "100" ; string s2 = "1000000" ; //Function call cout < < findDiff(s1, s2); return 0; }

Java

//Java program to find difference of two large numbers. import java.util.*; class GFG { //Returns true if str1 is smaller than str2. static boolean isSmaller(String str1, String str2) { //Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); if (n1 < n2) return true ; if (n2 < n1) return false ; for ( int i = 0 ; i < n1; i++) if (str1.charAt(i) < str2.charAt(i)) return true ; else if (str1.charAt(i)> str2.charAt(i)) return false ; return false ; } //Function for find difference of larger numbers static String findDiff(String str1, String str2) { //Before proceeding further, make sure str1 //is not smaller if (isSmaller(str1, str2)) { String t = str1; str1 = str2; str2 = t; } //Take an empty string for storing result String str = "" ; //Calculate length of both string int n1 = str1.length(), n2 = str2.length(); //Reverse both of strings str1 = new StringBuilder(str1).reverse().toString(); str2 = new StringBuilder(str2).reverse().toString(); int carry = 0 ; //Run loop till small string length //and subtract digit of str1 to str2 for ( int i = 0 ; i < n2; i++) { //Do school mathematics, compute difference of //current digits int sub = (( int )(str1.charAt(i) - '0' ) - ( int )(str2.charAt(i) - '0' ) - carry); //If subtraction is less then zero //we add then we add 10 into sub and //take carry as 1 for calculating next step if (sub < 0 ) { sub = sub + 10 ; carry = 1 ; } else carry = 0 ; str += ( char )(sub + '0' ); } //subtract remaining digits of larger number for ( int i = n2; i < n1; i++) { int sub = (( int )(str1.charAt(i) - '0' ) - carry); //if the sub value is -ve, then make it //positive if (sub < 0 ) { sub = sub + 10 ; carry = 1 ; } else carry = 0 ; str += ( char )(sub + '0' ); } //reverse resultant string return new StringBuilder(str).reverse().toString(); } //Driver code public static void main(String[] args) { String str1 = "978" ; String str2 = "12977" ; //Function call System.out.println(findDiff(str1, str2)); String s1 = "100" ; String s2 = "1000000" ; //Function call System.out.println(findDiff(s1, s2)); } } //This code is contributed by mits

Python3

# Python 3 program to find difference of two large numbers. # Returns true if str1 is smaller than str2. def isSmaller(str1, str2): # Calculate lengths of both string n1 = len (str1) n2 = len (str2) if (n1 < n2): return True if (n2 < n1): return False for i in range (n1): if (str1[i] < str2[i]): return True elif (str1[i]> str2[i]): return False return False # Function for find difference of larger numbers def findDiff(str1, str2): # Before proceeding further, make sure str1 # is not smaller if (isSmaller(str1, str2)): temp = str1 str1 = str2 str2 = temp # Take an empty string for storing result str3 = "" # Calculate length of both string n1 = len (str1) n2 = len (str2) # Reverse both of strings str1 = str1[:: - 1 ] str2 = str2[:: - 1 ] carry = 0 # Run loop till small string length # and subtract digit of str1 to str2 for i in range (n2): # Do school mathematics, compute difference of # current digits sub = (( ord (str1[i]) - ord ( '0' )) - ( ord (str2[i]) - ord ( '0' )) - carry) # If subtraction is less then zero # we add then we add 10 into sub and # take carry as 1 for calculating next step if (sub < 0 ): sub = sub + 10 carry = 1 else : carry = 0 str3 = str3 + str (sub) # subtract remaining digits of larger number for i in range (n2, n1): sub = (( ord (str1[i]) - ord ( '0' )) - carry) # if the sub value is -ve, then make it positive if (sub < 0 ): sub = sub + 10 carry = 1 else : carry = 0 str3 = str3 + str (sub) # reverse resultant string str3 = str3[:: - 1 ] return str3 # Driver code if __name__ = = "__main__" : str1 = "978" str2 = "12977"# Function call print (findDiff(str1, str2)) s1 = "100" s2 = "1000000"# Function call print (findDiff(s1, s2)) # This code is contributed by ChitraNayal

//C# program to find difference of two large numbers. using System; using System.Collections; class GFG { //Returns true if str1 is smaller than str2. static bool isSmaller( string str1, string str2) { //Calculate lengths of both string int n1 = str1.Length, n2 = str2.Length; if (n1 < n2) return true ; if (n2 < n1) return false ; for ( int i = 0; i < n1; i++) if (str1[i] < str2[i]) return true ; else if (str1[i]> str2[i]) return false ; return false ; } //Function for find difference of larger numbers static string findDiff( string str1, string str2) { //Before proceeding further, make sure str1 //is not smaller if (isSmaller(str1, str2)) { string t = str1; str1 = str2; str2 = t; } //Take an empty string for storing result string str = "" ; //Calculate length of both string int n1 = str1.Length, n2 = str2.Length; //Reverse both of strings char [] ch1 = str1.ToCharArray(); Array.Reverse(ch1); str1 = new string (ch1); char [] ch2 = str2.ToCharArray(); Array.Reverse(ch2); str2 = new string (ch2); int carry = 0; //Run loop till small string length //and subtract digit of str1 to str2 for ( int i = 0; i < n2; i++) { //Do school mathematics, compute difference of //current digits int sub = (( int )(str1[i] - '0' ) - ( int )(str2[i] - '0' ) - carry); //If subtraction is less then zero //we add then we add 10 into sub and //take carry as 1 for calculating next step if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += ( char )(sub + '0' ); } //subtract remaining digits of larger number for ( int i = n2; i < n1; i++) { int sub = (( int )(str1[i] - '0' ) - carry); //if the sub value is -ve, then make it //positive if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += ( char )(sub + '0' ); } //reverse resultant string char [] ch3 = str.ToCharArray(); Array.Reverse(ch3); return new string (ch3); } //Driver code public static void Main() { string str1 = "978" ; string str2 = "12977" ; //Function call Console.WriteLine(findDiff(str1, str2)); string s1 = "100" ; string s2 = "1000000" ; //Function call Console.WriteLine(findDiff(s1, s2)); } } //This code is contributed by mits

PHP

< ?php //PHP program to find difference of two large numbers. //Returns true if str1 is smaller than str2. function isSmaller( $str1 , $str2 ) { //Calculate lengths of both string $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); if ( $n1 < $n2 ) return true; if ( $n2 < $n1 ) return false; for ( $i =0; $i < $n1 ; $i ++) if ( $str1 [ $i ] < $str2 [ $i ]) return true; else if ( $str1 [ $i ]> $str2 [ $i ]) return false; return false; } //Function for find difference of larger numbers function findDiff( $str1 , $str2 ) { //Before proceeding further, make sure str1 //is not smaller if (isSmaller( $str1 , $str2 )){ $t = $str1 ; $str1 = $str2 ; $str2 = $t ; } //Take an empty string for storing result $str = "" ; //Calculate length of both string $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); //Reverse both of strings $str1 = strrev ( $str1 ); $str2 = strrev ( $str2 ); $carry = 0; //Run loop till small string length //and subtract digit of str1 to str2 for ( $i =0; $i < $n2 ; $i ++) { //Do school mathematics, compute difference of //current digits$sub =((ord( $str1 [ $i ])-ord( '0' ))-(ord( $str2 [ $i ])-ord( '0' ))- $carry ); //If subtraction is less then zero //we add then we add 10 into sub and //take carry as 1 for calculating next step if ( $sub < 0) { $sub = $sub + 10; $carry = 1; } else $carry = 0; $str .= chr ( $sub +48); } //subtract remaining digits of larger number for ( $i = $n2 ; $i < $n1 ; $i ++) { $sub = ((ord( $str1 [ $i ])-ord( '0' )) - $carry ); //if the sub value is -ve, then make it positive if ( $sub < 0) { $sub = $sub + 10; $carry = 1; } else $carry = 0; $str .= chr ( $sub +48); } //reverse resultant string $str = strrev ( $str ); return $str ; } //Driver code $str1 = "978" ; $str2 = "12977" ; //Function call echo findDiff( $str1 , $str2 ). "\n" ; $s1 = "100" ; $s2 = "1000000" ; //Function call echo findDiff( $s1 , $s2 ); //This code is contributed by mits ?>

输出如下

11999 0999900

优化的解决方案：
通过从末尾遍历它们, 可以避免前两个字符串反向操作。
以下是优化的解决方案。
C++

//C++ program to find difference of two large numbers. #include < bits/stdc++.h> using namespace std; //Returns true if str1 is smaller than str2, //else false. bool isSmaller(string str1, string str2) { //Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); if (n1 < n2) return true ; if (n2 < n1) return false ; for ( int i = 0; i < n1; i++) { if (str1[i] < str2[i]) return true ; else if (str1[i]> str2[i]) return false ; } return false ; } //Function for finding difference of larger numbers string findDiff(string str1, string str2) { //Before proceeding further, make sure str1 //is not smaller if (isSmaller(str1, str2)) swap(str1, str2); //Take an empty string for storing result string str = "" ; //Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); int diff = n1 - n2; //Initially take carry zero int carry = 0; //Traverse from end of both strings for ( int i = n2 - 1; i> = 0; i--) { //Do school mathematics, compute difference of //current digits and carry int sub = ((str1[i + diff] - '0' ) - (str2[i] - '0' ) - carry); if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str.push_back(sub + '0' ); } //subtract remaining digits of str1[] for ( int i = n1 - n2 - 1; i> = 0; i--) { if (str1[i] == '0' & & carry) { str.push_back( '9' ); continue ; } int sub = ((str1[i] - '0' ) - carry); if (i> 0 || sub> 0) //remove preceding 0's str.push_back(sub + '0' ); carry = 0; } //reverse resultant string reverse(str.begin(), str.end()); return str; } //Driver code int main() { string str1 = "88" ; string str2 = "1079" ; //Function call cout < < findDiff(str1, str2); return 0; }

Java

//Java program to find difference of two large numbers. class GFG { //Returns true if str1 is smaller than str2, //else false. static boolean isSmaller(String str1, String str2) { //Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); if (n1 < n2) return true ; if (n2 < n1) return false ; for ( int i = 0 ; i < n1; i++) { if (str1.charAt(i) < str2.charAt(i)) return true ; else if (str1.charAt(i)> str2.charAt(i)) return false ; } return false ; } //Function for finding difference of larger numbers static String findDiff(String str1, String str2) { //Before proceeding further, make sure str1 //is not smaller if (isSmaller(str1, str2)) { String t = str1; str1 = str2; str2 = t; } //Take an empty string for storing result String str = "" ; //Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); int diff = n1 - n2; //Initially take carry zero int carry = 0 ; //Traverse from end of both strings for ( int i = n2 - 1 ; i> = 0 ; i--) { //Do school mathematics, compute difference of //current digits and carry int sub = ((( int )str1.charAt(i + diff) - ( int ) '0' ) - (( int )str2.charAt(i) - ( int ) '0' ) - carry); if (sub < 0 ) { sub = sub + 10 ; carry = 1 ; } else carry = 0 ; str += String.valueOf(sub); } //subtract remaining digits of str1[] for ( int i = n1 - n2 - 1 ; i> = 0 ; i--) { if (str1.charAt(i) == '0' & & carry> 0 ) { str += "9" ; continue ; } int sub = ((( int )str1.charAt(i) - ( int ) '0' ) - carry); if (i> 0 || sub> 0 ) //remove preceding 0's str += String.valueOf(sub); carry = 0 ; } //reverse resultant string return new StringBuilder(str).reverse().toString(); } //Driver code public static void main(String[] args) { String str1 = "88" ; String str2 = "1079" ; //Function call System.out.println(findDiff(str1, str2)); } } //This code is contributed by mits

Python3

# Python3 program to find difference # of two large numbers. # Returns true if str1 is smaller than # str2, else false. def isSmaller(str1, str2):# Calculate lengths of both string n1 = len (str1) n2 = len (str2) if (n1 < n2): return True if (n2 < n1): return False for i in range (n1): if (str1[i] < str2[i]): return True elif (str1[i]> str2[i]): return Falsereturn False # Function for finding difference # of larger numbers def findDiff(str1, str2):# Before proceeding further, # make sure str1 is not smaller if (isSmaller(str1, str2)): str1, str2 = str2, str1 # Take an empty string for # storing result Str = ""# Calculate lengths of both string n1 = len (str1) n2 = len (str2) diff = n1 - n2# Initially take carry zero carry = 0# Traverse from end of both strings for i in range (n2 - 1 , - 1 , - 1 ):# Do school mathematics, compute # difference of current digits # and carry sub = (( ord (str1[i + diff]) - ord ( '0' )) - ( ord (str2[i]) - ord ( '0' )) - carry) if (sub < 0 ): sub + = 10 carry = 1 else : carry = 0 Str + = chr (sub + ord ( '0' ))# Subtract remaining digits of str1[] for i in range (n1 - n2 - 1 , - 1 , - 1 ): if (str1[i] = = '0' and carry): Str + = '9' continuesub = ( ord (str1[i]) - ord ( '0' )) - carry# Remove preceding 0's if (i> 0 or sub> 0 ): Str + = chr (sub + ord ( '0' ))carry = 0 # Reverse resultant string Str = Str [:: - 1 ]return Str # Driver code str1 = "88" str2 = "1079" # Function call print (findDiff(str1, str2)) # This code is contributed by avanitrachhadiya2155

//C# program to find difference of //two large numbers. using System; class GFG { //Returns true if str1 is smaller //than str2, else false. static bool isSmaller( string str1, string str2) { //Calculate lengths of both string int n1 = str1.Length, n2 = str2.Length; if (n1 < n2) return true ; if (n2 < n1) return false ; for ( int i = 0; i < n1; i++) { if (str1[i] < str2[i]) return true ; else if (str1[i]> str2[i]) return false ; } return false ; } //Function for finding difference of //larger numbers static string findDiff( string str1, string str2) { //Before proceeding further, //make sure str1 is not smaller if (isSmaller(str1, str2)) { string t = str1; str1 = str2; str2 = t; } //Take an empty string for //storing result String str = "" ; //Calculate lengths of both string int n1 = str1.Length, n2 = str2.Length; int diff = n1 - n2; //Initially take carry zero int carry = 0; //Traverse from end of both strings for ( int i = n2 - 1; i> = 0; i--) { //Do school mathematics, compute //difference of current digits and carry int sub = ((( int )str1[i + diff] - ( int ) '0' ) - (( int )str2[i] - ( int ) '0' ) - carry); if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += sub.ToString(); } //subtract remaining digits of str1[] for ( int i = n1 - n2 - 1; i> = 0; i--) { if (str1[i] == '0' & & carry> 0) { str += "9" ; continue ; } int sub = ((( int )str1[i] - ( int ) '0' ) - carry); if (i> 0 || sub> 0) //remove preceding 0's str += sub.ToString(); carry = 0; } //reverse resultant string char [] aa = str.ToCharArray(); Array.Reverse(aa); return new string (aa); } //Driver code public static void Main() { String str1 = "88" ; String str2 = "1079" ; //Function call Console.WriteLine(findDiff(str1, str2)); } } //This code is contributed by mits

PHP

< ?php //PHP program to find difference of two //large numbers. //Returns true if str1 is smaller than //str2, else false. function isSmaller( $str1 , $str2 ) { //Calculate lengths of both string $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); if ( $n1 < $n2 ) return true; if ( $n2 < $n1 ) return false; for ( $i = 0; $i < $n1 ; $i ++) { if ( $str1 [ $i ] < $str2 [ $i ]) return true; else if ( $str1 [ $i ]> $str2 [ $i ]) return false; } return false; } //Function for finding difference //of larger numbers function findDiff( $str1 , $str2 ) { //Before proceeding further, make //sure str1 is not smaller if (isSmaller( $str1 , $str2 )) { $t = $str1 ; $str1 = $str2 ; $str2 = $t ; } //Take an empty string for storing result $str = "" ; //Calculate lengths of both string $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); $diff = $n1 - $n2 ; //Initially take carry zero $carry = 0; //Traverse from end of both strings for ( $i = $n2 - 1; $i> = 0; $i --) { //Do school mathematics, compute //difference of current digits and carry $sub = ((ord( $str1 [ $i + $diff ]) - ord( '0' )) - (ord( $str2 [ $i ]) - ord( '0' )) - $carry ); if ( $sub < 0) { $sub = $sub + 10; $carry = 1; } else $carry = 0; $str .= chr ( $sub + ord( "0" )); } //subtract remaining digits of str1[] for ( $i = $n1 - $n2 - 1; $i> = 0; $i --) { if ( $str1 [ $i ] == '0' & & $carry> 0) { $str .= "9" ; continue ; } $sub = (ord( $str1 [ $i ]) - ord( '0' ) - $carry ); if ( $i> 0 || $sub> 0) //remove preceding 0's $str .= chr ( $sub + ord( "0" )); $carry = 0; } //reverse resultant string return strrev ( $str ); } //Driver code $str1 = "88" ; $str2 = "1079" ; //Function call print (findDiff( $str1 , $str2 )); //This code is contributed by chandan_jnu ?>

输出如下