Saya mencoba untuk menggeneralisasi jawaban optimal untuk Masalah 1 di Project Euler, dan menyadari bahwa saat menggunakan inklusi /exclusion method, jawaban yang keluar salah jika Anda masuk dalam daftar di mana salah satu nomor adalah kelipatan dari salah satu nomor lain dalam daftar.

Misalnya, dengan batas 1000, dan daftar [3, 5, 6, 8], jawabannya keluar sebagai 306004, tetapi jawabannya HARUS keluar sebagai 266824. Ini karena 6 adalah kelipatan 3, dan perlu dihapus.

Saya datang dengan kode berikut untuk menghapus kelipatan asing dari daftar:

def cleanMults(mults):
    m = sorted(mults)
    x = [m[0]]
    for i in range(len(m) - 1, 0, -1):
        multFound = False
        for j in range(i - 1, -1, -1):
            if m[i] % m[j] == 0: 
                multFound = True
                break
        if multFound == False: x.append(m[i])
    return sorted(x)

Di sini saya menyortir daftar (untuk berjaga-jaga jika itu rusak), lalu mulai dengan elemen terakhir dalam daftar, membandingkan setiap elemen dengan setiap elemen lainnya. Jika elemen yang dibagi dengan elemen lain menghasilkan sisa 0, maka kita menetapkan multFound = True, break, dan tidak menambahkannya ke daftar solusi. Jika tidak, jika tidak ada pembagi yang ditemukan, kami menambahkannya ke daftar.

Pertanyaan saya adalah, apakah ada cara yang lebih optimal untuk melakukan ini? Bahkan mengabaikan pengurutan, ini berjalan dalam waktu O(n^2). Saya tahu ada cara untuk membandingkan dua daftar dalam waktu O(n log(n)), tetapi ini tidak persis sama dengan itu. Adakah yang punya ide atau solusi di sini?

0
Ryan McGregor 8 Januari 2021, 02:52

1 menjawab

Inilah yang saya miliki saat ini:

import time 
from math import prod 
from itertools import combinations as co 

def SoM(lim, mul): 
    n = (lim - 1) //mul 
    return (n * (n + 1) * mul) // 2 

def inex(lim, mults): 
    ans = 0 
    for i in range(len(mults)): 
        for j in co(mults, i + 1): 
            ans += (-1)**i * SoM(lim, prod(list(j))) 
    return ans

def cleanMults(mults):
    m = sorted(mults)
    x = [m[0]]
    for i in range(len(m) - 1, 0, -1):
        multFound = False
        for j in range(i - 1, -1, -1):
            if m[i] % m[j] == 0: multFound = True
        if multFound == False: x.append(m[i])
    return sorted(x)

def toString(mults):
    if len(mults) == 1: return str(list(mults)[0])
    s = 'or ' + str(list(mults)[-1])
    for i in range(len(mults) - 2, -1, -1):
        s = str(list(mults)[i]) + ', ' + s
    return s

def SumOfMults(lim, mults):
    #Declare variables
    start = time.time()
    strnums, m = '', cleanMults(mults)

    #Solve the problem
    ans = str(inex(lim, m))
        
    #Print the results
    print('The sum of all of the multiples of ')
    print(toString(mults) + ' below ' + str(lim) + ' is ' + ans + '.')
    print('This took ' + str(time.time() - start) + ' seconds to calculate.')

Saya berasumsi tidak ada duplikat, meskipun jika ada, yang harus saya lakukan adalah melemparkan daftar ke satu set, lalu kembali ke daftar lagi.

Itu kata kamu:

"Untuk menggeneralisasi ini ke lebih banyak faktor, bilangan komposit harus dikurangi k-1 kali, di mana k adalah jumlah faktor."

Bisakah Anda menjelaskan lebih detail tentang apa yang Anda maksud, dengan contoh?

Dalam contoh seperti daftar [3, 5, 26], 26 adalah bilangan komposit, dan hanya memiliki 2 faktor (2, dan 13), jadi jika saya tidak salah paham, jumlah semua faktor dari 26 ke atas ke batas perlu dikurangi dari total sekali?

Dengan logika saya, saat ini saya melakukan hal berikut:

Sum3 + sum5 + sum26 - sum78 (26 * 3) - sum130 (26 * 5) - sum15 (3 * 5) + sum1170 (3 * 5 * 26).

Apakah Anda menyarankan ada cara yang lebih efisien untuk menghitung ini?

0
Ryan McGregor 8 Januari 2021, 09:10