Alice ve Şekerler problemi

1

Bir kaç gündür su soruyla uğraşıyorum. Sizlerle de paylaşmak istedim. Öncelikle soru şu.

Alice şekerleri seven bir kızdır ve şekerci dükkanına girer. Şekerci dükkanındaki tüm paketler (1,3,5,7 …) halinde tek sayılar içeriyor. Alice sadece paketlerdeki şeker sayıları ardışıksa şeker alabiliyor. Örneğin 45 şeker almak istediğinde üç farklı biçimde alabilir.

  1. {5,7,9,11,13}
  2. {13,15,17}
  3. {45}

Alice’in sonsuz parası varsa ve şekercinin de sonsuz paketi var Alice in herhangi bir şeker sayısı karşısında kaç farklı biçimde şeker alabileceğini bulan programı yazınız.

Bu örnek için,
girdi: 45
çıktı: 3

Bunun için ilk yazdığım kod şu ama zaman ve bellek şartlarını her girdi için sağlamıyor. Bu yüzden kodu hızlandırmaya çalışıyorum. Fikirlerinize açığım.

N = int(input())
out = 0
li = [i for i in range(1,N+2,2)]
tane = int(N**(1/2))
while tane>0:
    for bas in range(0,len(li)-tane+1):
        if sum(li[bas:tane+bas]) == N:
            out += 1
            break
        if sum(li[bas:tane+bas]) > N:
            break   

    tane = tane - 1

print(out)
2

Huffman algoritmasına bakabilirsin

4

Merhabalar,

Paylaştığınız algoritmayı sonsuz_function isminde bir fonksiyon haline getirdim.

def sonsuz_function(N):
    out = 0
    li = [i for i in range(1, N + 2, 2)]
    tane = int(N ** (1 / 2))
    while tane > 0:
        for bas in range(0, len(li) - tane + 1):
            if sum(li[bas:tane + bas]) == N:
                out += 1
                break
            if sum(li[bas:tane + bas]) > N:
                break
        tane = tane - 1
    return out

Benim izlediğim algoritma da şöyle:

def two_ended_range(d: int):
    return [j - d // 2 + (0 if d % 2 or j < d // 2 else 1) for j in range(d)]


def range_values(n: int, d: int):
    r = [n // d + 2 * i for i in two_ended_range(d=d)]
    if not r[0] % 2:
        r = [r[i] + (1 if d % 2 or i < d // 2 else -1) for i in range(len(r))]
    return r


def how_many_different_ways(n: int):
    count = 0
    divisor = 1 if n % 2 else 2
    while (values := range_values(n=n, d=divisor))[0] > 0:
        if (
            sum(values) == n
            and
            all(abs(values[i] - values[i + 1]) == 2 for i in range(len(values) - 1))
        ):
            count += 1
        divisor += 2
    return count

Şimdi, sonsuz_function ile how_many_different_ways fonksiyonlarını karşılaştıralım:

import timeit

t1 = timeit.timeit(lambda: sonsuz_function(pow(10, 6)), number=1)
t2 = timeit.timeit(lambda: how_many_different_ways(pow(10, 6)), number=1)
print(
    f"sonsuz_function: {t1}, sonuç: {sonsuz_function(pow(10, 6))}\n"
    f"how_many_different_ways: {t2}, sonuç: {how_many_different_ways(pow(10, 6))}"
)

Aldığım sonuç:

sonsuz_function: 4.278696199995466, sonuç: 18
how_many_different_ways: 0.07718149999709567, sonuç: 18
1 Beğeni
5

İzninizle bu algoritmanın mantığını açıklayayım:

Öncelikle, soruyu şu şekilde yeniden soralım:

1’den n + 1’e kadar olan ardışık tek sayılar kümesi içinde toplamı n olan ve elemanları ardışık dizilmiş kaç tane alt küme vardır?

Şimdi, öncelikle örnek bir seriyi zihnimizde bir canlandırmaya çalışalım:

n = 99 olsa;

99’un kendisi bir tek sayı olduğu için ve [99] alt kümesinin elemanlarının toplamı 99 olduğu için, [n], range(1, n + 1, 2)'in alt kümesi olur. n çift sayı olursa [n] bir alt küme olmaz.

99’un yarısı 49.5, bu değeri 49’a yuvarlıyorum. 49’un 2 eksiği 47, 2 fazlası 51, 47 + 51 = 98. Zaten ardışık da değiller, aralarındaki fark 2 değil 4. Dolayısıyla range(1, n + 1, 2) kümesinin toplamı n olan 2 elemanlı bir alt kümesi yokmuş.

range(1, n + 1, 2) kümesinin toplamı n eden 3 elemanlı bir alt kümesi var mı bakalım: 99 / 3 = 33. 33 merkezde yer alan değer, 2 eksiği 31, 2 fazlası 35 olur. Bu 3 değeri toplayalım 31 + 33 + 35 = 99. Demek ki range(1, n + 1, 2) kümesinin toplamı n eden 3 elemanlı bir alt kümesi varmış.

Dolayısıyla, burada n’i sürekli d isminde bir bölene bölüp, o bölümde yer alan alt kümenin ne olduğunu buluyoruz. Sonra bu alt kümenin elemanlarını toplayıp, toplamın n’e eşit olup olmadığını ve küme elemanlarının ardışık olup olmadığını buluyoruz. Çünkü yukarda gördüğünüz gibi, alt kümenin uzunluğu çift sayı ve böleni 2 olduğunda, tam merkezde yer alan n // 2 değeri düşer. dolayısıyla elemanlar arasındaki fark 4’e çıkar.

Örneğin:
[47, 51]

Bu yukardaki işlem, bölen sürekli 2 artırılarak devam eder. 1 artırmıyoruz çünkü n sayısı tekse elemanlarının toplamı tek olan ve uzunluğu çift sayı olan bir alt küme olamaz. Veya, n sayısı çiftse, elemanlarının toplamı çift sayı olan ve uzunluğu da tek sayı olan bir alt küme olamaz. Dolayısıyla artırmayı 2 birim yapmak lazım.

n = 99 için, döngü şöyle values değerleri üretir:

kümeler, toplam
[99] 99  # 1.
[31, 33, 35] 99  # 2.
[15, 17, 19, 21, 23] 95
[9, 11, 13, 15, 17, 19, 21] 105
[3, 5, 7, 9, 11, 13, 15, 17, 19] 99  # 3.
[-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 99
3  # Toplam alt küme sayısı

while döngüsü, üretilen alt küme, range(1, n + 1) aralığından çıkmaya başladığı zaman yani values = [-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] durumunda durdurulur.

3 Beğeni
6

Ben de soyle yaptim:

def possible_consecutive_odd_sums(number):
	ways = 0
	for summands in range(1, number):
		p = summands * (summands - 1)
		if p > number:
			break
		numbase = number - p
		if numbase % summands == 0:
			n = numbase // summands
			if n % 2 == 1:
#				print(f"{number} = {' + '.join([str(n + 2*i) for i in range(summands)])}")
				ways += 1
	return ways

sonsuz_function:               4.338458116981201, sonuç: 18
how_many_different_ways:       0.07976276497356594, sonuç: 18
possible_consecutive_odd_sums: 0.00012113992124795914, sonuç: 18
4 Beğeni
7

Güzel. :smiling_face_with_three_hearts:

1 Beğeni
8

Sizden esinlenip şöyle bir kod daha yazdım. Test sürelerini geçiyor ama yavaşlığını kontrol etmedim.

def function_sonsuz(N):
    out = 0
    tek = False
    bas = 2
    if N%2==1:
        tek = True
        bas = 1
    kk = int(N**(1/2))+1
    for t1 in range(bas,kk,2):
        if N%t1==0:
            t2 = N/t1
            if t1%2==0 and t2%2==0 and not tek:
                out += 1
            elif t1%2==1 and t2%2==1 and tek:
                out += 1
            else:
                pass

    return out

Edit: Şöyle bi gıdım daha hızlandı.

def fonk2(N):
    out = 0
    tek = False
    bas = 2
    if N%2==1:
        tek = True
        bas = 1
    kk = int(N**(1/2))+1
    while bas<=kk:
        if N%bas==0:
            t2 = N/bas
            if bas%2==0 and t2%2==0 and not tek:
                out += 1
            elif bas%2==1 and t2%2==1 and tek:
                out += 1
            else:
                pass
        bas += 2
    return out
2 Beğeni
9 
fonk2: 6.749999738531187e-05, sonuç: 18
how_many_different_ways: 0.06521599999905447, sonuç: 18
possible_consecutive_odd_sums: 0.00011330000052112155, sonuç: 18

İşte bu! :heart_eyes:

1 Beğeni
11

Ben de şöyle bir kod yazdım;

image