मैं बिगइंटर का उपयोग किए बिना जावा में करात्सुबा एल्गोरिदम लागू करने की कोशिश कर रहा हूं। मेरा कोड केवल तभी लागू होता है जब दोनों पूर्णांक समान होते हैं & में अंकों की संख्या समान होती है। मुझे सही जवाब नहीं मिला है, हालांकि मुझे जवाब मिलता है जो सही के करीब है। उदाहरण के लिए मुझे 14 9 मिलते हैं जब 12 * 12। मैं यह नहीं समझ सकता कि मेरे कोड में क्या गलत है क्योंकि मेरा मानना है कि मैंने सबकुछ सही किया है (पुस्तक द्वारा)। मेरा कोड यहाँ है।बिगइंटर उपयोग के बिना करात्सुबा एल्गोरिदम
public static void main(String[] args) {
long ans=karatsuba(12,12);
System.out.println(ans);
}
private static long karatsuba(long i, long j) {
if (i<10 || j<10){
return i*j;
}
int n=getCount(i);
long a=(long) (i/Math.pow(10, n/2));
long b=(long) (i%Math.pow(10, n/2));
long c=(long) (j/Math.pow(10, n/2));
long d=(long) (j%Math.pow(10, n/2));
long first=karatsuba(a,c);
long second=karatsuba(b,d);
long third=karatsuba(a+b,c+d);
return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10,n/2))+third));
}
private static int getCount(long i) {
String totalN=Long.toString(i);
return totalN.length();
}
संपादित करें:
Ziyao वी के लिए धन्यवाद, समस्या "तीसरे" की जगह किया गया था "दूसरी" द्वारा। हालांकि मेरे पास अब एक और मुद्दा है जो है:
अगर करत्सुबा (1234,5678) कहा जाता है तो मुझे सही जवाब मिलता है, हालांकि जब मैं करत्सुबा (5678,1234) कहता हूं तो मुझे सही जवाब नहीं मिलता है। क्या किसी को संभवतः इसके कारण का पता चल सकता है? मेरे अद्यतन कोड है:
public static void main(String[] args) {
//wrong answer
long ans=karatsuba(5678,1234);
System.out.println(ans);
//correct answer
long ans1=karatsuba(1234,5678);
System.out.println(ans1);
}
private static long karatsuba(long i, long j) {
if (i<10 || j<10){
return i*j;
}
int n=getCount(i);
long a=(long) (i/Math.pow(10, n/2));
long b=(long) (i%Math.pow(10, n/2));
long c=(long) (j/Math.pow(10, n/2));
long d=(long) (j%Math.pow(10, n/2));
long first=karatsuba(a,c);
long second=karatsuba(b,d);
long third=karatsuba(a+b,c+d);
return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10, n/2))+second));
}
अद्यतन:
मैं के लिए "n/2" मूल्य को ख़त्म कर में कामयाब रहे, इसलिए यह समस्या लेकिन यदि संख्या चार से अधिक अंक उपयोग किया जाता है बग उत्पन्न हल करती है।
public static void main(String[] args) {
System.out.println(Math.round(5.00/2));
//correct answer
long ans=karatsuba(5678,1234);
System.out.println(ans);
//correct answer
long ans1=karatsuba(1234,5678);
System.out.println(ans1);
//wrong answer
long ans2=karatsuba(102456,102465);
System.out.println(ans2);
}
private static long karatsuba(long i, long j) {
if (i<10 || j<10){
return i*j;
}
double n=Math.round(getCount(i));
long a=(long) (i/Math.pow(10, Math.round(n/2)));
long b=(long) (i%Math.pow(10, Math.round(n/2)));
long c=(long) (j/Math.pow(10, Math.round(n/2)));
long d=(long) (j%Math.pow(10, Math.round(n/2)));
long first=karatsuba(a,c);
long second=karatsuba(b,d);
long third=karatsuba(a+b,c+d);
return ((long) ((first*Math.pow(10, Math.round(n)))+((third-second-first)*Math.pow(10, Math.round(n/2)))+second));
}
private static double getCount(long i) {
String totalN=Long.toString(i);
return totalN.length();
}
किसी BigInteger का उपयोग कर तो कृपया मुझे पता है है बिना बड़ी संख्या (चार से अधिक अंक) के लिए समाधान के साथ आता है: यहाँ मेरी अद्यतन कोड है। धन्यवाद।
आप दौर या विभाजन करने से पहले एक पूर्णांक के लिए Math.pow परिणाम काटना चाहिए? –
आपकी GetCount विधि कैसे कार्यान्वित की जाती है? अगर मुझे सही ढंग से याद आता है और आपकी getCount विधि अपने पैरामीटर में अंकों की संख्या लौटाती है, तो आपको 'n' 'max (getCount (i), getCount (j)) सेट करना चाहिए। – jarnbjo
यह एक साधारण संस्करण है यह मानते हुए कि दोनों संख्याएं भी संख्याओं के बराबर हैं और उनके पास हैं। – Khan