Kiểm tra xem một số nguyên có phải là số nguyên của một số khác

Question

Đây là một số interview question: "Cho 2 số nguyên x và y, hãy kiểm tra xem x có phải là số nguyên của y" (ví dụ x = 8 và y = 2 câu trả lời hay không " true ", và cho x = 10 và y = 2" false ").

Các giải pháp rõ ràng là:

int n = y; while(n < x) n *= y; return n == x

Bây giờ tôi đang suy nghĩ về làm thế nào để cải thiện nó.

Tất nhiên, tôi có thể kiểm tra một số trường hợp đặc biệt: ví dụ: cả hai số x và y phải là số lẻ hoặc số chẵn, nghĩa là chúng tôi có thể kiểm tra bit ít quan trọng nhất là x và y. Tuy nhiên tôi tự hỏi nếu tôi có thể cải thiện các thuật toán lõi chính nó.

Answer 1

Bạn nên làm tốt hơn để liên tục chia y thành x. Lần đầu tiên bạn nhận được một số không khác, bạn biết x không phải là số nguyên của y.

while (x%y == 0) x = x/y 
return x == 1 

Điều này giải quyết điểm lẻ/chẵn của bạn trên lần lặp đầu tiên.

Answer 2

Nó có nghĩa log _y (x) phải là một số nguyên . Không cần bất kỳ vòng lặp nào. trong O (1) thời gian

public class PowerTest { 

    public static boolean isPower(int x, int y) { 
     double d = Math.log(Math.abs(x))/Math.log(Math.abs(y)); 

     if ((x > 0 && y > 0) || (x < 0 && y < 0)) { 
      if (d == (int) d) { 
       return true; 
      } else { 
       return false; 
      } 
     } else if (x > 0 && y < 0) { 
      if ((int) d % 2 == 0) { 
       return true; 
      } else { 
       return false; 
      } 
     } else { 
      return false; 
     } 
    } 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

     System.out.println(isPower(-32, -2)); 
     System.out.println(isPower(2, 8)); 
     System.out.println(isPower(8, 12)); 
     System.out.println(isPower(9, 9)); 
     System.out.println(isPower(-16, 2)); 
     System.out.println(isPower(-8, -2)); 
     System.out.println(isPower(16, -2)); 
     System.out.println(isPower(8, -2)); 
    } 

} 

Answer 3

tôi sẽ thực hiện các chức năng như vậy:

bool IsWholeNumberPower(int x, int y) 
{ 
    double power = log(x)/log(y); 
    return floor(power) == power; 
} 

này không cần kiểm tra trong phạm vi một vùng châu thổ như là phổ biến với so sánh dấu chấm động, kể từ khi chúng tôi kiểm tra lại toàn bộ số.

Answer 4

Trên suy nghĩ thứ hai, đừng làm điều này. Nó không hoạt động tiêu cực x và/hoặc y. Lưu ý rằng tất cả các câu trả lời khác dựa trên log được trình bày ngay bây giờ cũng bị hỏng theo cách giống hệt nhau.

Sau đây là một giải pháp chung nhanh (trong Java):

static boolean isPow(int x, int y) { 
    int logyx = (int)(Math.log(x)/Math.log(y)); 
    return pow(y, logyx) == x || pow(y, logyx + 1) == x; 
} 

đâu pow() là một chức năng nguyên lũy thừa như sau trong Java:

static int pow(int a, int b) { 
    return (int)Math.pow(a, b); 
} 

(này hoạt động do với bảo đảm sau đây được cung cấp bởi Math.pow: "Nếu cả hai đối số là số nguyên, thì kết quả là chính xác bằng kết quả toán học của việc tăng đối số đầu tiên lên sức mạnh của đối số thứ hai ... ")

Lý do để đi với logarit thay vì phân đoạn lặp lại là hiệu suất: trong khi log is slower than division, nó chậm hơn bởi một bội số cố định nhỏ. Đồng thời nó loại bỏ sự cần thiết cho một vòng lặp và do đó cung cấp cho bạn một thuật toán hằng số thời gian.

Answer 5

này sẽ cho số mũ trong thời gian O (log N) bước sau:

#define MAX_POWERS 100 

int is_power(unsigned long x, unsigned long y) { 
    int i; 
    unsigned long powers[MAX_POWERS]; 
    unsigned long last; 
    last = powers[0] = y; 

    for (i = 1; last < x; i++) { 
    last *= last; // note that last * last can overflow here! 
    powers[i] = last; 
    } 
    while (x >= y) { 
    unsigned long top = powers[--i]; 
    if (x >= top) { 
     unsigned long x1 = x/top; 
     if (x1 * top != x) return 0; 
     x = x1; 
    } 
    } 
    return (x == 1); 
} 

Số âm không được xử lý bằng mã này, nhưng nó có thể được thực hiện easyly với một số mã có điều kiện khi i = 1

Answer 6

Trong trường hợp y là 2, có một cách tiếp cận nhanh chóng tránh được sự cần thiết phải lặp lại. Cách tiếp cận này có thể được mở rộng đến các trường hợp trong đó y là một số công suất lớn hơn của 2.

Nếu x là công suất 2, biểu diễn nhị phân là x. Có một thuật toán bit-fiddling khá đơn giản để đếm các bit trong một số nguyên trong thời gian O (log n) trong đó n là chiều rộng bit của một số nguyên. Nhiều bộ vi xử lý cũng có hướng dẫn chuyên biệt có thể xử lý điều này như là một hoạt động đơn, nhanh như (ví dụ) một số nguyên phủ định.

Để mở rộng cách tiếp cận, trước tiên, hãy thực hiện một cách tiếp cận hơi khác một chút để kiểm tra một bit. Đầu tiên xác định vị trí của bit ít quan trọng nhất. Một lần nữa, có một thuật toán bit-fiddling đơn giản, và nhiều bộ xử lý có hướng dẫn chuyên môn nhanh.

Nếu bit này là bit duy nhất, thì (1 << pos) == x. Lợi thế ở đây là nếu bạn đang thử nghiệm cho một sức mạnh của 4, bạn có thể kiểm tra cho pos % 2 == 0 (bit duy nhất là ở một vị trí thậm chí). Kiểm tra sức mạnh của bất kỳ sức mạnh của hai, bạn có thể kiểm tra cho pos % (y >> 1) == 0.

Về nguyên tắc, bạn có thể làm điều gì đó tương tự để thử nghiệm quyền hạn 3 và quyền hạn của 3. Vấn đề là bạn cần một máy hoạt động ở cơ số 3, điều này khó xảy ra. Bạn chắc chắn có thể kiểm tra bất kỳ giá trị x để xem nếu đại diện của nó trong cơ sở y có một số không khác, nhưng bạn sẽ làm nhiều công việc mà bạn đã làm. Việc khai thác ở trên thực tế là các máy tính hoạt động ở dạng nhị phân.

Có lẽ không đáng làm trong thế giới thực.

Answer 7

Điều này có vẻ khá nhanh đối với các số dương vì nó tìm thấy giới hạn dưới và trên cho công suất mong muốn và sau đó áp dụng tìm kiếm nhị phân.

#include <iostream> 
#include <cmath> 
using namespace std; 

//x is the dividend, y the divisor. 
bool isIntegerPower(int x, int y) 
{ 
    int low = 0, high; 
    int exp = 1; 
    int val = y; 
    //Loop by changing exponent in the powers of 2 and 
    //Find out low and high exponents between which the required exponent lies. 
    while(1) 
    { 
     val = pow((double)y, exp); 
     if(val == x) 
      return true; 
     else if(val > x) 
      break; 
     low = exp; 
     exp = exp * 2; 
     high = exp; 
    } 
    //Use binary search to find out the actual integer exponent if exists 
    //Otherwise, return false as no integer power. 
    int mid = (low + high)/2; 
    while(low < high) 
    { 
     val = pow((double)y, mid); 
     if(val > x) 
     { 
      high = mid-1; 
     } 
     else if(val == x) 
     { 
      return true; 
     } 
     else if(val < x) 
     { 
      low = mid+1; 
     } 
     mid = (low + high)/2; 
    } 
    return false; 
} 

int main() 
{ 
    cout<<isIntegerPower(1024,2); 
} 

Answer 8

Câu trả lời trước là chính xác, tôi thích câu trả lời của Paul nhất. Nó đơn giản và sạch sẽ. Đây là việc thực hiện Java của những gì ông đề nghị:

public static boolean isPowerOfaNumber(int baseOrg, int powerOrg) { 
    double base = baseOrg; 
    double power = powerOrg; 

    while (base % power == 0) 
     base = base/power; 
    // return true if base is equal 1 
    return base == 1; 
} 

Answer 9

double a=8; 
    double b=64; 

    double n = Math.log(b)/Math.log(a); 
    double e = Math.ceil(n); 

    if((n/e) == 1){ 
     System.out.println("true"); 
    } else{ 
     System.out.println("false"); 
    } 

Answer 10

Nếu bạn có quyền truy cập đến sức mạnh lớn nhất của y, có thể được trang bị bên trong datatype yêu cầu, đây là một cách thực sự trơn tru của giải này vấn đề.

Giả sử, đối với trường hợp của chúng tôi, y == 3. Vì vậy, chúng tôi cần kiểm tra xem x có phải là công suất của 3.

Do đó chúng tôi cần kiểm tra xem số nguyên x có phải là công suất của 3 không, hãy bắt đầu suy nghĩ về vấn đề này về thông tin đã có tay.

1162261467 là công suất lớn nhất của 3 có thể vừa với Java int.
1162261467 = 3^19 + 0

x đã cho có thể được biểu thị là [(a power of 3) + (some n)]. Tôi nghĩ rằng nó là khá tiểu học để có thể chứng minh rằng nếu n là 0 (mà xảy ra iff x là một sức mạnh của 3), 1162261467 % x = 0.

Vì vậy, để kiểm tra xem một số nguyên nhất định x có phải là số ba không, hãy kiểm tra xem x > 0 && 1162261467 % x == 0.

Tổng quát. Để kiểm tra nếu một số nguyên được cho là x là một lũy thừa của một số nguyên được cho là y, hãy kiểm tra xem x > 0 && Y % x == 0: Y là công suất lớn nhất của y có thể phù hợp với một kiểu dữ liệu nguyên.

Ý tưởng chung là nếu A là một số công suất Y, A có thể được biểu thị là B/Ya, trong đó a là một số nguyên và A < B. Nó tuân theo nguyên tắc chính xác tương tự cho A > B. Trường hợp A = B là trường tiểu học.

Answer 11

tôi tìm thấy giải pháp này // Check for Nếu A có thể được diễn tả như sức mạnh của hai số nguyên

int isPower(int A) 
    { 
    int i,a; 
    double p; 
    if(A==1) 
    return 1; 
    for(int a=1; a<=sqrt(A);++a) 
    { 
     p=log(A)/log(a); 
     if(p-int(p)<0.000000001) 
     return 1; 
    } 
    return 0; 
    } 

binarycoder.org

Answer 12

Đây là một phiên bản Python trong đó đặt lại với nhau những ý tưởng của @salva và @ Axn và được sửa đổi để không tạo ra bất kỳ số nào lớn hơn số đã cho và chỉ sử dụng bộ nhớ đơn giản (đọc, "không có danh sách") bằng cách lặp đi lặp lại với số lượng yêu thích:

def perfect_base(b, n): 
    """Returns True if integer n can be expressed as b**e where 
    n is a positive integer, else False.""" 

    assert b > 1 and n >= b and int(n) == n and int(b) == b 

    # parity check 
    if not b % 2: 
     if n % 2: 
      return False # b,n is even,odd 
     if b == 2: 
      return n & (n - 1) == 0 
     if not b & (b - 1) and n & (n - 1): 
      return False # b == 2**m but n != 2**M 
    elif not n % 2: 
     return False # b,n is odd,even 

    while n >= b: 
     d = b 
     while d <= n: 
      n, r = divmod(n, d) 
      if r: 
       return False 
      d *= d 
    return n == 1