מספר נ ובסיס שלילי negBase ניתן לנו אנחנו צריכים לייצג את n בבסיס השלילי הזה. בסיס שלילי עובד בדומה לבסיס חיובי. לדוגמה בבסיס 2 נכפיל סיביות ל-1 2 4 8 וכן הלאה כדי לקבל את המספר האמיתי בעשרוני. במקרה של בסיס -2 עלינו להכפיל ביטים עם 1 -2 4 -8 וכן הלאה כדי לקבל מספר בעשרוני.
דוגמאות:
אתרים כמו coomeet
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
ניתן לייצג מספר לכל בסיס שלילי באותו הליך (עיין שבוע לפרטים). למען הפשטות (כדי להיפטר מתווים A B וכו' בפלט) אנו מאפשרים לבסיס שלנו להיות בין -2 ל-10 בלבד.
אנחנו יכולים לפתור בעיה זו בדומה לפתרון בעיה עם בסיסים חיוביים אבל דבר אחד שחשוב לזכור הוא שהשאריות תמיד יהיו חיוביות בין אם נעבוד עם בסיס חיובי או בסיס שלילי אבל ברוב המהדרים התוצאה של חלוקת מספר שלילי במספר שלילי מעוגלת לכיוון 0 בדרך כלל משאירה שארית שלילית.
אז בכל פעם שנקבל שארית שלילית נוכל להמיר אותה לחיובית כמו להלן
Let n = (?negBase) * quotient + remainder = (?negBase) * quotient + negBase ? negBase + negBase = (?negBase) * (quotient + 1) + (remainder + negBase). So if after doing 'remainder = n % negBase' and 'n = n/negBase' we get negative remainder we do following. remainder = remainder + (-negBase) n = n + 1 Example : n = -4 negBase = -3 In C++ we get remainder = n % negBase = -4/-3 = -1 n = n/negBase [Next step for base conversion] = -4/-3 = 1 To avoid negative remainder we do remainder = -1 + (-negBase) = -1 - (-3) = 2 n = n + 1 = 1 + 1 = 2.
אז כאשר נקבל שארית שלילית, נהפוך אותה לחיובית על ידי הוספת ערך מוחלט של בסיס אליה והוספת 1 למנה שלנו.
הגישה המוסברת לעיל מיושמת בקוד שלהלן
מהו שם משתמשC++
// C/C++ program to convert n into negative base form #include using namespace std; // Utility method to convert integer into string string toString(int n) { string str; stringstream ss; ss << n; ss >> str; return str; } // Method to convert n to base negBase string toNegativeBase(int n int negBase) { // If n is zero then in any base it will be 0 only if (n == 0) return '0'; string converted = ''; while (n != 0) { // Get remainder by negative base it can be // negative also int remainder = n % negBase; n /= negBase; // if remainder is negative add abs(base) to // it and add 1 to n if (remainder < 0) { remainder += (-negBase); n += 1; } // convert remainder to string add into the result converted = toString(remainder) + converted; } return converted; } // Driver code to test above methods int main() { int n = 13; int negBase = -2; cout << toNegativeBase(n negBase); return 0; }
Java // Java program to convert n into // negative base form class GFG { // Method to convert n to base negBase static String toNegativeBase(int n int negBase) { // If n is zero then in any base // it will be 0 only if (n == 0) return '0'; String converted = ''; while (n != 0) { // Get remainder by negative base // it can be negative also int remainder = n % negBase; n /= negBase; // if remainder is negative // add Math.abs(base) to it // and add 1 to n if (remainder < 0) { remainder += (-negBase); n += 1; } // convert remainder to String add into the result converted = String.valueOf(remainder) + converted; } return converted; } // Driver Code public static void main(String[] args) { int n = 13; int negBase = -2; System.out.print(toNegativeBase(n negBase)); } } // This code is contributed by 29AjayKumar
Python3 # Python 3 program to convert n into # negative base form # Method to convert n to base negBase def toNegativeBase(n negBase): # If n is zero then in any base it # will be 0 only if (n == 0): return '0' converted = '01' while (n != 0): # Get remainder by negative base # it can be negative also remainder = n % (negBase) n = int(n/negBase) # if remainder is negative add # abs(base) to it and add 1 to n if (remainder < 0): remainder += ((-1) * negBase) n += 1 # convert remainder to string add # into the result converted = str(remainder) + converted return converted # Driver Code if __name__ == '__main__': n = 13 negBase = -2 print(toNegativeBase(n negBase)) # This code is contributed by # Surendra_Gangwar
C# // C# program to convert n into // negative base form using System; class GFG { // Method to convert n to base negBase static String toNegativeBase(int n int negBase) { // If n is zero then in any base // it will be 0 only if (n == 0) return '0'; String converted = ''; while (n != 0) { // Get remainder by negative base // it can be negative also int remainder = n % negBase; n /= negBase; // if remainder is negative // add Math.Abs(base) to it // and add 1 to n if (remainder < 0) { remainder += (-negBase); n += 1; } // convert remainder to String add into the result converted = String.Join('' remainder) + converted; } return converted; } // Driver Code public static void Main(String[] args) { int n = 13; int negBase = -2; Console.Write(toNegativeBase(n negBase)); } } // This code is contributed by Rajput-Ji
JavaScript <script> // JavaScript program to convert n into // negative base form // Method to convert n to base negBase function toNegativeBase(n negBase) { // If n is zero then in any base // it will be 0 only if (n == 0) return '0'; let converted = '01'; while (n != 0) { // Get remainder by negative base // it can be negative also let remainder = (-1)*(Math.abs(n) % Math.abs(negBase)); n = parseInt(n/negBase); // if remainder is negative // add Math.abs(base) to it // and add 1 to n if (remainder < 0) { remainder += ((-1)*negBase); n += 1; } // convert remainder to String add into the result converted = remainder.toString() + converted; } return converted; } // Driver Code let n = 13; let negBase = -2; document.write(toNegativeBase(n negBase)''); // This code is contributed by shinjanpatra </script>
תְפוּקָה:
11101
מורכבות זמן: עַל)
מרחב עזר: O(1)
הפניה:
https://en.wikipedia.org/wiki/Negative_base