Блог

Укажите диапазон чисел [p, q], найдите количество экземпляров, которые являются произведением x ^ t * y ^ v.
Например:
диапазон [200, 250], где x = 3 и y=5.
225 = 9 * 25 = 3^2 * 5^2
Другой пример:
диапазон [1,1], где x=3 и y =5.
1 = 1 * 1 = 3^0 * 5^0

Я не мог найти способ закодировать эту проблему. Существует ли алгоритм для этого?

 def a_function():
    count = 0
    for i in range(200, 250):
        if (i % 3 == 0) or (i % 5 == 0):
            count  = 1
    return count
 

Вы могли бы попробовать следующее. Сгенерируйте все возможные степени в этом диапазоне и умножьте их одну на другую, чтобы проверить, соответствуют ли они нашему диапазону.

 import math
range_start=200
range_end=250
x = 3
y=5
x_list=[]
y_list=[]

count=0
while pow(x,count)<range_end:
    x_list.append(pow(x,count))
    count =1

count=0
while pow(y,count)<range_end:
    y_list.append(pow(y,count))
    count =1

# print(x_list)
# print(y_list)

ans=[]

for i in x_list:
    for j in y_list:
        if i*j>=range_start and i*j<=range_end:
            ans.append(i*j)


print(ans)
 

Далее, поскольку списки отсортированы, мы можем оптимизировать пространство поиска с помощью двоичного поиска.

Я чувствую, что для этого есть эффективный алгоритм, но, к сожалению, я не могу придумать его сразу…

То, что я сделал, в значительной степени является методом перебора, но вот он…

 def is_in_range(min_range, max_range, x, y, i, j):
    product = x**i * y**j
    if product > min_range and product < max_range:
        return True, product
    return False, product

def find_number_in_range(min_range, max_range, x, y, i, j):
    in_range = False
    while not in_range:
        in_range, product = is_in_range(min_range, max_range, x, y, i, j)
        if in_range:
            return product
        i  = 1
        in_range, product = is_in_range(min_range, max_range, x, y, i, j)
        if in_range:
            return product
        j  = 1
        in_range, product = is_in_range(min_range, max_range, x, y, i, j)
        if in_range:
            return product

        if product > max_range:
            print("Could not find any.")
            break
    return
 

Я нашел относительно более эффективный алгоритм, использующий минимальные кучи. Поскольку вам нужны только числа вида x^t*y^v , мы можем поддерживать минимальную кучу, чтобы только выдвигать и выдвигать соответствующие потенциальные значения в указанном диапазоне.

Вот код на Python с некоторым объяснением:

 from heapq import heappop, heappush
from math import log, pow


# input_range is like [200,250] ; eg input_range=tuple(200,250) - values inclusive
def get_pattern_numbers_in_range(input_range, x: int, y: int):
    # Let x be smaller than y; if otherwise just swap
    if x > y:
        x, y = y, x

    starting_range, ending_range = input_range

    # Now maintain a Min-Heap to only consider values that follow the required pattern of x^t*y^v
    value_heap = [x*y]
    # value_heap = [starting_val]
    input_set = {x*y}
    result_list = []

    while True:
        print("Min-Heap::", value_heap)
        pop_value = heappop(value_heap)
        if pop_value > ending_range:
            return result_list
        if pop_value >= starting_range:
            result_list.append(pop_value)
        if pop_value*x not in input_set:
            input_set.add(pop_value * x)
            heappush(value_heap, pop_value * x)
        if pop_value*y not in input_set:
            input_set.add(pop_value * y)
            heappush(value_heap, pop_value * y)


res = get_pattern_numbers_in_range((200, 250), 3, 5)
print(res)
 

Вывод:

 [225]
 

Время-сложность:

 Let min_xy = min(x, y)
Let log_N_base_xy = log(N)/log(min_xy)

Time-complexity = O((N/min_xy) * log(log_N_base_xy))
 

Большие тестовые примеры:

 res = get_pattern_numbers_in_range((2000000, 2500000), 3, 5)
 

Вывод:

 [2109375, 2278125, 2460375]
 

Подкрасться к тому, как выглядит минимальная куча на каждом этапе:

 Min-Heap:: [15]
Min-Heap:: [45, 75]
Min-Heap:: [75, 135, 225]
Min-Heap:: [135, 225, 375]
Min-Heap:: [225, 375, 405, 675]
Min-Heap:: [375, 675, 405, 1125]
Min-Heap:: [405, 675, 1125, 1875]
Min-Heap:: [675, 1215, 1125, 1875, 2025]
Min-Heap:: [1125, 1215, 2025, 1875, 3375]
Min-Heap:: [1215, 1875, 2025, 3375, 5625]
Min-Heap:: [1875, 3375, 2025, 5625, 3645, 6075]
Min-Heap:: [2025, 3375, 6075, 5625, 3645, 9375]
Min-Heap:: [3375, 3645, 6075, 5625, 9375, 10125]
Min-Heap:: [3645, 5625, 6075, 10125, 9375, 16875]
Min-Heap:: [5625, 9375, 6075, 10125, 16875, 10935, 18225]
Min-Heap:: [6075, 9375, 10935, 10125, 16875, 18225, 28125]
Min-Heap:: [9375, 10125, 10935, 28125, 16875, 18225, 30375]
Min-Heap:: [10125, 16875, 10935, 28125, 30375, 18225, 46875]
Min-Heap:: [10935, 16875, 18225, 28125, 30375, 46875, 50625]
Min-Heap:: [16875, 28125, 18225, 50625, 30375, 46875, 32805, 54675]
Min-Heap:: [18225, 28125, 32805, 50625, 30375, 46875, 54675, 84375]
Min-Heap:: [28125, 30375, 32805, 50625, 84375, 46875, 54675, 91125]
Min-Heap:: [30375, 50625, 32805, 91125, 84375, 46875, 54675, 140625]
Min-Heap:: [32805, 50625, 46875, 91125, 84375, 140625, 54675, 151875]
Min-Heap:: [46875, 50625, 54675, 91125, 84375, 140625, 151875, 98415, 164025]
Min-Heap:: [50625, 84375, 54675, 91125, 164025, 140625, 151875, 98415, 234375]
Min-Heap:: [54675, 84375, 140625, 91125, 164025, 234375, 151875, 98415, 253125]
Min-Heap:: [84375, 91125, 140625, 98415, 164025, 234375, 151875, 253125, 273375]
Min-Heap:: [91125, 98415, 140625, 253125, 164025, 234375, 151875, 273375, 421875]
Min-Heap:: [98415, 164025, 140625, 253125, 421875, 234375, 151875, 273375, 455625]
Min-Heap:: [140625, 164025, 151875, 253125, 421875, 234375, 455625, 273375, 295245, 492075]
Min-Heap:: [151875, 164025, 234375, 253125, 421875, 492075, 455625, 273375, 295245, 703125]
Min-Heap:: [164025, 253125, 234375, 273375, 421875, 492075, 455625, 703125, 295245, 759375]
Min-Heap:: [234375, 253125, 455625, 273375, 421875, 492075, 759375, 703125, 295245, 820125]
Min-Heap:: [253125, 273375, 455625, 295245, 421875, 492075, 759375, 703125, 820125, 1171875]
Min-Heap:: [273375, 295245, 455625, 703125, 421875, 492075, 759375, 1171875, 820125, 1265625]
Min-Heap:: [295245, 421875, 455625, 703125, 1265625, 492075, 759375, 1171875, 820125, 1366875]
Min-Heap:: [421875, 703125, 455625, 820125, 885735, 492075, 759375, 1171875, 1366875, 1265625, 1476225]
Min-Heap:: [455625, 703125, 492075, 820125, 885735, 1476225, 759375, 1171875, 1366875, 1265625, 2109375]
Min-Heap:: [492075, 703125, 759375, 820125, 885735, 1476225, 2109375, 1171875, 1366875, 1265625, 2278125]
Min-Heap:: [703125, 820125, 759375, 1171875, 885735, 1476225, 2109375, 2278125, 1366875, 1265625, 2460375]
Min-Heap:: [759375, 820125, 1476225, 1171875, 885735, 2460375, 2109375, 2278125, 1366875, 1265625, 3515625]
Min-Heap:: [820125, 885735, 1476225, 1171875, 1265625, 2460375, 2109375, 2278125, 1366875, 3515625, 3796875]
Min-Heap:: [885735, 1171875, 1476225, 1366875, 1265625, 2460375, 2109375, 2278125, 3796875, 3515625, 4100625]
Min-Heap:: [1171875, 1265625, 1476225, 1366875, 2657205, 2460375, 2109375, 2278125, 3796875, 4100625, 3515625, 4428675]
Min-Heap:: [1265625, 1366875, 1476225, 2278125, 2657205, 2460375, 2109375, 4428675, 3796875, 4100625, 3515625, 5859375]
Min-Heap:: [1366875, 2278125, 1476225, 3796875, 2657205, 2460375, 2109375, 4428675, 5859375, 4100625, 3515625, 6328125]
Min-Heap:: [1476225, 2278125, 2109375, 3796875, 2657205, 2460375, 6328125, 4428675, 5859375, 4100625, 3515625, 6834375]
Min-Heap:: [2109375, 2278125, 2460375, 3796875, 2657205, 6834375, 6328125, 4428675, 5859375, 4100625, 3515625, 7381125]
Min-Heap:: [2278125, 2657205, 2460375, 3796875, 3515625, 6834375, 6328125, 4428675, 5859375, 4100625, 7381125, 10546875]
Min-Heap:: [2460375, 2657205, 6328125, 3796875, 3515625, 6834375, 10546875, 4428675, 5859375, 4100625, 7381125, 11390625]
Min-Heap:: [2657205, 3515625, 6328125, 3796875, 4100625, 6834375, 10546875, 4428675, 5859375, 11390625, 7381125, 12301875]

Final result:
[2109375, 2278125, 2460375]