#practiceLinkDiv { display: none !important; }Číslo Carol je celé číslo v tvare 4n- 2(n+1)- 1. Ekvivalentný vzorec je (2n-1)2- 2.
Zaujímavá nehnuteľnosť:
Pre n > 2 je binárne vyjadrenie n-tého čísla Carol n-2 po sebe idúcich jedna nula v strede a n + 1 ďalšia po sebe idúca jednička. Príklad n = 4 číslo koledy je 223 a binárne číslo 223 je 11011111 tu n-2 = 4-2 = 2 po sebe idúce počnúc, potom jedna 0 v strede a potom n + 1 = 4 + 1 = 5 po sebe idúcich.
Ak je dané číslo n, úlohou je nájsť n-té číslo Carol. Prvých pár čísel koled je -1 7 47 223 959... atď.
Príklady:
Input : n = 2 Output: 7 Input : n = 4 Output: 223Recommended Practice Carol Numbers Skúste to! C++
// C++ program to find n'th Carol number #include
# Python program to find n'th Carol number def carol(n): # a**b is a ^ b in python result = (2**n) - 1 return result * result - 2 # driver program to run the case n = 4 print (carol(n))
/* Java program to find n'th Carol number */ class GFG { static int carol(int n) { double tmp = Math.pow(2 n) - 1; return (int)tmp; } public static void main(String[] args) { int n = 4; System.out.println(carol(n)); } }
/* C# program to find n'th Carol number */ using System; class GFG { static int carol(int n) { int result = (int)Math.Pow(2 n) - 1; return result * result - 2; } // Driver code public static void Main() { int n = 4; Console.WriteLine(carol(n)); } } // This code is contributed by vt_m.
// PHP program to find // n'th Carol number // Function to find // n'th carol number function carol($n) { $result = pow(2 $n) - 1; return $result * $result - 2; } // Driver Code $n = 4; echo carol($n); // This code is contributed by ajit ?> <script> /* Javascript program to find n'th Carol number */ function carol(n) { let result = Math.pow(2 n) - 1; return result * result - 2; } let n = 4; document.write(carol(n)); </script>
výstup:
223
Časová zložitosť y: O(log n) pre funkciu pow
Pomocný priestor: O(1)