cách tạo số cho các yếu tố chính của chúng, nhưng với số mũ không xác định?

Question

Bản sao có thể xảy ra:
nth ugly number
Find the Kth least number for expression (2^x)*(3^y)*(5^z)

Tôi đang tự hỏi làm thế nào để giải quyết vấn đề này một cách nhanh chóng và thanh lịch:

Chúng ta định nghĩa "xấu xí" mỗi số n có thể được viết dưới dạng: 2^x * 3^y * 5^z ;, trong đó x, y và z là số tự nhiên. Tìm số thứ xấu xí thứ 1500.

Ví dụ: là người đầu tiên con số "xấu xí" là:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... 

Tôi đã cố gắng để giải quyết vấn đề này bằng brute-force, theo cách này:

import itertools as it 

def is_ugly(n): 
    '''Return `True` if *n* is an ugly number.''' 

    if n == 1: 
     return True 
    while not n % 2: 
     n //= 2 
    while not n % 3: 
     n //= 3 
    while not n % 5: 
     n //= 5 
    return n == 1 

def nth_ugly(n): 
    '''Return the nth ugly number.''' 

    num = 0 
    for i in it.count(1): 
     if is_ugly(i): 
      num += 1 
      if num == n: 
       return i 

Nhưng phải mất khá nhiều thời gian, và tôi muốn tìm một giải pháp nhanh hơn và tốt hơn.

Tôi biết các yếu tố chính của số xấu, nhưng tôi không thể nghĩ ra cách để tạo ra những con số này theo đúng thứ tự.

Tôi nghĩ rằng phải có một cách để tạo ra những con số này mà không cần phải kiểm tra tất cả các con số. Vấn đề là nó có vẻ như số mũ của các yếu tố chính được phân phối khá ngẫu nhiên.

Nhìn vào bảng này:

n |number| x | y | z | 
------------------------ 
1 | 1 | 0 | 0 | 0 | 
------------------------ 
2 | 2 | 1 | 0 | 0 | 
------------------------ 
3 | 3 | 0 | 1 | 0 | 
------------------------ 
4 | 4 | 2 | 0 | 0 | 
------------------------ 
5 | 5 | 0 | 0 | 1 | 
------------------------ 
6 | 6 | 1 | 1 | 0 | 
------------------------ 
7 | 8 | 3 | 0 | 0 | 
------------------------ 
8 | 9 | 0 | 2 | 0 | 
------------------------ 
9 | 10 | 1 | 0 | 1 | 
------------------------ 
10 | 12 | 2 | 1 | 0 | 
------------------------ 
11 | 15 | 0 | 1 | 1 | 
------------------------ 
12 | 16 | 4 | 0 | 0 | 
------------------------ 
13 | 18 | 1 | 2 | 0 | 
------------------------ 
14 | 20 | 2 | 0 | 1 | 
------------------------ 
15 | 24 | 3 | 1 | 0 | 
------------------------ 

Như bạn thấy x, y và z giá trị dường như không tuân theo bất kỳ quy tắc.

Ai đó có thể tìm ra giải pháp cho vấn đề này không?

Tôi đang nghĩ đến việc cố gắng phân chia vấn đề ở các phần khác nhau. Vì vấn đề được xác định bởi sự ngẫu nhiên của số mũ, tôi có thể cố gắng tạo ra độc lập các lũy thừa của 2s, 3s, 5s và sau đó là số của biểu mẫu 2^x * 3^y, 2^x * 5^z v.v. Và cuối cùng đặt chúng lại với nhau, nhưng tôi không biết nếu điều này sẽ giải quyết vấn đề của tôi.

Answer 1

Đây là giải pháp hoàn chỉnh. O (n) phức tạp, nó tạo ra mọi số một lần và theo thứ tự.

# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF 

n = 15 
bases = [2, 3, 5] 

nums = [1] * n 
candidates_indexes = [0 for _ in bases] 
candidates = [base for base in bases] 

for i in range(1, n): 
    nextn = min(candidates) 
    nums[i] = nextn 

    for index, val in enumerate(candidates): 
     if val == nextn: 
      candidates_indexes[index] += 1 
      candidates[index] = bases[index] * nums[candidates_indexes[index]] 

print(nums) 

Answer 2

Tôi đề nghị bạn giải quyết điều này từng bước và lưu trữ tất cả các số xấu xí mà bạn tìm thấy trong danh sách.

Khi kiểm tra một số cho sự xấu xa đó, bạn chỉ cần kiểm tra xem nó là một lần số của bạn 2, 3 hoặc 5.

EDIT: Tôi chỉ cố gắng thực hiện điều đó như thế này

ugly = [1] 
candidate = 2 
while len(ugly) < 1500: 
    for u in ugly: 
     if any([(u * x == candidate) for x in (2, 3 ,5)]): 
      ugly.append(candidate) 
      break 
    candidate += 1 

print ugly[-1] 

nhưng cách tiếp cận này trì trệ một cách vô vọng. Quá ngây thơ. :) Sử dụng một số loại sàng của Eratosthenes hơn.

Answer 3

sử dụng danh sách (n trong mã sau) để lưu trữ tất cả các số xấu trước, số xấu xí tiếp theo là số min (n * 2, n * 3, n * 5) lớn hơn rồi n [ -1]:

n = [1] 
while len(n) < 1500: 
    n.append(min([next(x*s for x in n if x*s>n[-1]) for s in (2,3,5)]))  
print n[-1] 

Đó là giải pháp O (n^2), vì vậy đừng thử số lớn.

Answer 4

Đây là giải pháp sử dụng một đống. Ý tưởng là chúng tôi theo dõi các số mũ cùng với sản phẩm xấu xí. Đối với mỗi lần lặp lại, thuật toán thực hiện tối đa 3 hoạt động find_min và 3 hoạt động chèn, Các hàm find_mins có thể dư thừa vì bạn có thể nhận được bằng cách thêm một vào bất kỳ số mũ nào, và có ba số mũ. Chúng tôi thực hiện chèn ba lần vì chúng tôi thêm một số vào mỗi số mũ và chèn nó vào heap. Để tìm số thứ n xấu, chúng ta phải thực hiện các phép toán N là 6 * O (log n), do đó thuật toán có độ phức tạp về thời gian của O (n log n). Chính bản thân nó, vì nó chỉ có thể tăng thêm một lượng không đổi cho mỗi lần lặp lại, là SPACE (O (n))

>>> import heapq, itertools 
>>> class UglyGen(object): 
...  def __init__(self, x, y, z): 
...   self.x, self.y, self.z = x, y, z 
...   self.value = 2**self.x * 3**self.y * 5**self.z 
...  def incr(self): 
...   x, y, z = self.x, self.y, self.z 
...   return (UglyGen(x+1, y, z), 
...     UglyGen(x, y+1, z), 
...     UglyGen(x, y, z+1)) 
...  def __lt__(self, other): 
...   if not isinstance(other, UglyGen): 
...    return NotImplemented 
...   return self.value < other.value 
... 
>>> def gen_ugly(): 
...  gens = [UglyGen(0, 0, 0)] 
...  last = 0 
...  while gens: 
...   while gens[0].value == last: 
...    heapq.heappop(gens) 
...   top = heapq.heappop(gens) 
...   succ_items = top.incr() 
...   for succ in succ_items: 
...    heapq.heappush(gens, succ) 
...   last = top.value 
...   yield last 
... 
>>> def find_nth_ugly(n): 
...  for n0, u in itertools.izip(xrange(n), gen_ugly()): 
...   pass 
...  return u 
... 
>>> find_nth_ugly(15) 
24