Python ծրագիր՝ Jumbo GCD Subarray-ը գտնելու համար

Jumbo GCD-ին կարելի է վերաբերել՝ գտնելու զանգվածի առավելագույն երկարությամբ ենթազանգվածի ամենամեծ ընդհանուր բաժանարարը (GCD): GCD-ն դրական ամբողջ թվերի բազմություն է, որը բաժանում է բոլոր թվերը՝ առանց մնացորդ ունենալու: Մենք կարող ենք պարզել Jumbo GCD ենթաշարքը՝ օգտագործելով երկու տարբեր մոտեցումներ, ինչպիսիք են Brute force և Optimized մոտեցումը, օգտագործելով նախածանցային գումարները: Jumbo GCD ենթախմբի լուծումը ներկայացված է այս հոդվածում համապատասխան օրինակներով: Brute force մոտեցումը կարող է օգտագործվել դիտարկվող զանգվածի բոլոր հնարավոր ենթազանգվածները ստուգելու և առանձին ենթազանգվածի GCD-ն հաշվարկելու համար։

Օրինակ 1. Գտնել Jumbo GCD ենթաշարքը՝ օգտագործելով Brute force մոտեցումը:

Բարդ խնդիր լուծելու համար մենք կարող ենք օգտագործել Brute force մոտեցումը։ Դա տրված խնդրի հնարավոր լուծմանը հասնելու պարզ միջոց է։ Jumbo GCD ենթաշարքի խնդրի վերաբերյալ.

Կոդի բացատրության և ձևավորման քայլեր, օրինակ 1

Քայլ 1. Բացեք Jupyter Notebook-ը Anaconda-ի հուշում և սկսեք գրել կոդը դրա բջիջում:

Քայլ 2. Ներմուծեք «զանգված» մոդուլը:

Քայլ 3. Օգտագործեք «gcd()» ֆունկցիան՝ Էվկլիդեսյան ալգորիթմի միջոցով երկու թվերի GCD արժեքը հաշվարկելու համար: Այստեղ մենք դիտարկում ենք երկու թվեր, ինչպիսիք են a-ն և b-ը, եթե b=0, ապա GCD-ն այլ կերպ է, a-ի և b-ի GCD-ն նույնն է, ինչ b-ը, իսկ մնացորդը՝ a%b-ի:

Քայլ 4. «jumbo_gcd_brute_force» ֆունկցիան օգտագործում է «Brute force» մոտեցումը՝ Jumbo GCD ենթադասարանը որոնելու համար:

Քայլ 5. Նախաձեռնեք «արդյունք» փոփոխականը և սահմանեք այս փոփոխականը զրոյի: GCD արժեքը կարող է պահվել «արդյունք» փոփոխականում:

Քայլ 6. Ինդեքսավորումը սկսվում է o ինդեքսից մինչև n-1 ինդեքսը, որտեղ n-ը զանգվածի երկարությունն է: Այն կրկնում է ենթաշարքի բոլոր հնարավոր դիրքերը զրոյից մինչև n-1 ինդեքսը:

Քայլ 7. Ստուգեք, թե արդյոք վերջին ենթախմբի GCD-ն պետք է ավելի մեծ լինի, քան ընթացիկ արդյունքը, այնուհետև թարմացրեք «արդյունք» փոփոխականը նոր առավելագույնով: GCD.

Քայլ 8. Վերջապես, ստուգեք ենթազանգվածի GCD-ի վերջնական արժեքը տվյալ զանգվածի հետ միասին «արդյունք»-ում:

Կոդ Jumbo Brute force մոտեցման համար

Օրինակ

import array
def gcd(a, b):
    # Function to calculate the GCD of two numbers
    while b:
        a, b = b, a % b
    return a
def jumbo_gcd_brute_force(arr):
    n = len(arr)
    result = 0
    for i in range(n):
        for j in range(i, n):
            subarray_gcd = arr[i]
            for k in range(i + 1, j + 1):
                subarray_gcd = gcd(subarray_gcd, arr[k])
            result = max(result, subarray_gcd)

    return result
 # Example usage:
arr = [8, 12, 6, 4, 10,14]
print("Array:", arr)
print("Brute Force approach - Jumbo GCD subarray:", jumbo_gcd_brute_force(arr))

Արդյունք

Array: [8, 12, 6, 4, 10, 14]
Brute Force approach - Jumbo GCD subarray: 14

Brute force մոտեցումը վերցնում է ենթազանգվածների յուրաքանչյուր հնարավոր համակցություն: Այն հաշվարկում է առանձին մեկի GCD-ն և գտնում է երաշխավորված առավելագույն GCD ենթաշարքը:

Օրինակ 2. Գտնել Jumbo GCD ենթաշարքը՝ օգտագործելով Օպտիմիզացված մոտեցումը:

Jumbo GCD ենթախմբի խնդիրը լուծելու համար մենք կարող ենք օգտագործել մեկ այլ մոտեցում, որը կոչվում է օպտիմալացված մոտեցում: Այս մոտեցման նպատակն է նվազեցնել ժամանակի բարդությունը՝ համեմատած Brute force մոտեցման հետ՝ օգտագործելով GCD-ի հատկությունները:

Կոդի բացատրության և ձևավորման քայլեր, օրինակ 2

Քայլ 1. Բացեք Jupyter Notebook-ը Anaconda-ի հուշում և սկսեք գրել կոդը դրա բջիջում:

Քայլ 2. Ներմուծեք «զանգված» մոդուլը:

Քայլ 3. Օգտագործեք ‘gcd()’ ֆունկցիան՝ Էվկլիդեսյան ալգորիթմի միջոցով երկու թվերի GCD արժեքը հաշվարկելու համար: Այստեղ մենք դիտարկում ենք երկու թվեր, ինչպիսիք են a-ն և b-ը, եթե b=0, ապա GCD-ն այլ կերպ է, a-ի և b-ի GCD-ն նույնն է, ինչ b-ը, իսկ մնացածը՝ a%b-ը: :

Քայլ 4. «jumbo_gcd_optimized» ֆունկցիան օգտագործում է օպտիմիզացված մոտեցումը` գտնելու jumbo GCD ենթախումբը:

Քայլ 5. Նախաձեռնեք «արդյունք» փոփոխականը և սահմանեք այս փոփոխականը զրոյի: GCD արժեքը կարող է պահվել «արդյունք» փոփոխականում:

Քայլ 6. Ինդեքսավորումը սկսվում է o ինդեքսից մինչև n-1 ինդեքսը, որտեղ n-ը զանգվածի երկարությունն է: Այն կրկնում է ենթաշարքի բոլոր հնարավոր դիրքերը զրոյից մինչև n-1 ինդեքսը:

Քայլ 7. Կրկնել 6-րդ քայլը՝ կրկնելով զանգվածի վրայով հակառակ հաջորդականությամբ/հակադարձ հերթականությամբ, որը սկսվում է n-1 ինդեքսից մինչև զրո ինդեքսը:

Քայլ 8. Հաշվեք GCD-ն ընթացիկ տարրին իր «արդյունք»-ով և համապատասխանաբար թարմացրեք այն:

Քայլ 9. Ստուգեք, թե արդյոք վերջին ենթախմբի GCD-ն պետք է ավելի մեծ լինի, քան ընթացիկ արդյունքը, այնուհետև թարմացրեք «արդյունք» փոփոխականը նոր առավելագույնով: GCD.

Քայլ 10. Վերջապես, ստուգեք ենթազանգվածի GCD-ի վերջնական արժեքը տվյալ զանգվածի հետ միասին «արդյունք»-ում:

Օպտիմիզացված մոտեցման ծածկագիր

Օրինակ

import array
def gcd(a, b):
    # Function is used to calculate the GCD of two numbers
    while b:
        a, b = b, a % b
    return a

def jumbo_gcd_optimized(arr):
    n = len(arr)
    prefix_gcd = [0] * n
    suffix_gcd = [0] * n
    prefix_gcd[0] = arr[0]
 # Forward iteration:
   
    for i in range(1, n):
        prefix_gcd[i] = gcd(prefix_gcd[i - 1], arr[i])
    suffix_gcd[n - 1] = arr[n - 1]
# Backward iteration:
    for i in range(n - 2, -1, -1):
        suffix_gcd[i] = gcd(suffix_gcd[i + 1], arr[i])
    result = max(suffix_gcd[1], prefix_gcd[n - 2])
    for i in range(1, n - 1):
        result = max(result, gcd(prefix_gcd[i - 1], suffix_gcd[i + 1]))
    
    return result
# Example usage:
arr = [8, 12, 6, 4, 10,14]
print("Array:", arr)
print("Optimized approach - Jumbo GCD subarray:", jumbo_gcd_optimized(arr))

Արդյունք

Array: [8, 12, 6, 4, 10, 14]
Optimized approach - Jumbo GCD subarray: 2

Օպտիմիզացված մոտեցումը հաշվարկում է նախածանցների և վերջածանցների GCD զանգվածները և համապատասխանաբար պահպանում է իրական զանգվածի ինչպես նախածանցների, այնպես էլ վերջածանցների GCD-ները: Այն կրկնվում է զանգվածի վրա՝ բացառելով Ist և վերջին տարրերը, այնուհետև հաշվարկում է առավելագույնը: GCD՝ վերցնելով նաև GCD նախածանցը և վերջածանցը: Այս մոտեցումն ավելի արդյունավետ է ավելի մեծ զանգվածների համար:

Եզրակացություն

Jumbo GCD ենթադասարան հոդվածում, օգտագործելով երկու տարբեր մոտեցումներ օրինակներով, այս մեթոդները ցույց են տալիս, թե ինչպես կարելի է գտնել ենթաշարքի jumbo GCD արժեքը: Առաջին մեթոդը հաշվարկում է տվյալ զանգվածի արժեքը՝ ստանալու համար GCD ենթազանգվածի արժեքը, իսկ երկրորդ մեթոդն ունի նույն նպատակը՝ արդյունք ստանալու համար, բայց ոճը տարբեր է: Brute force մոտեցման ժամանակային բարդությունը O (n^3) է, մինչդեռ օպտիմիզացված մոտեցումն ունի O(n) ժամանակային բարդություն: Արդյունքում, օպտիմիզացված մոտեցումն ավելի արդյունավետ է, քան Brute force մոտեցումը ավելի մեծ զանգվածների համար: Մենք կարող ենք դիտարկել jumbo GCD-ի հնարավոր կիրառումը հատուկ սցենարներում, ինչպիսիք են զանգվածի մշակումը, ազդանշանի մշակումը, ծածկագրությունը և այլն: