Rehber: Çarpım tablosundaki farklı sayıların adedi üzerine

Konu Başlıkları Gizle

1 Problem ne?
2 Çözüm?
3 E, daha iyisi mi var?
1. 3.1 Adım adım...
  1. 3.1.1 Tek satır
  2. 3.1.2 İki satır
  3. 3.1.3 Üç satır
  4. 3.1.4 Dört satır
2. 3.2 Genelleştirme vakti
3. 3.3 Adı belli
4. 3.4 Kod vakti!
5. 3.5 Ufak bir not
4 Bu kadarcıktı
5 İyi Sosyaller!

Merhaba,

Şu konudaki problemi çözmeye çalışırken elde ettiğim bir alt problemin çözümünü anlatmak istedim: Project Euler - 29. problem nasıl çözülür?

Çözümde programlamanın rolü esasen gözlemlerle elde edilen matematiksel formülleri koda dökmek. Hâliyle biraz matematik ağırlıklı bir anlatım olacak, umarım sevenleriniz vardır. : )
Özellikle sayma yöntemlerini alakadar eden bir problem, e tabii.

İyi okumalar. Kafanıza bir kısım takılırsa sormaktan çekinmeyin.

Problem ne?

Amacımız, çarpım tablosundaki belirli bir alt tablonun içinde kaç farklı sayı olduğunu bulmak. 10 x 20'lik bir tablonun üzerinden örnek vermek gerekirse:

Tabloları Google Sheets ile şuradan yardım alarak hazırladım.

Burada tablonun 9. ile 20. sütunları arası olacak şekilde 10 x 12'lik bir alt tablonun seçildiğini görüyoruz. Bu alt tablonun bir de sadece farklı sayıların işaretlenmiş hâlini görelim:

Koyu kırmızılı karelerin sayısı, bize bu alt tablo için cevabı veriyor: 88.

Çözüm?

Alt tablonun ilk ve son satır ve sütun numaralarını parametreleştirip problemin genel hâlini çözen kod yazmak oldukça basit:

C++:

#include <bits/stdc++.h>

using namespace std;

int main() {
    cout << "Ilk ve son satir numaralari: ";
    int ilk_satir, son_satir;
    cin >> ilk_satir >> son_satir;

    cout << "Ilk ve son sutun numaralari: ";
    int ilk_sutun, son_sutun;
    cin >> ilk_sutun >> son_sutun;

    int toplam_sayi_adedi = (son_satir - ilk_satir + 1) *
                            (son_sutun - ilk_sutun + 1);

    unordered_set<int> farkli_sayilar;

    for (int satir = ilk_satir; satir <= son_satir;
         satir++) {
        for (int sutun = ilk_sutun; sutun <= son_sutun;
             sutun++) {
            farkli_sayilar.insert(satir * sutun);
        }
    }

    cout << toplam_sayi_adedi << " adet sayi icinde toplam "
         << farkli_sayilar.size() << " farkli sayi var.\n";
}

Python:

print("Ilk ve son satir numaralari:", end=" ")
ilk_satir, son_satir = map(int, input().split())

print("Ilk ve son sutun numaralari:", end=" ")
ilk_sutun, son_sutun = map(int, input().split())

toplam_sayi_adedi = (son_satir - ilk_satir + 1) * (
    son_sutun - ilk_sutun + 1
)

farkli_sayilar = set()

for satir in range(ilk_satir, son_satir + 1):
    for sutun in range(ilk_sutun, son_sutun + 1):
        farkli_sayilar.add(satir * sutun)

print(
    f"{toplam_sayi_adedi} adet sayi icinde toplam"
    f" {len(farkli_sayilar)} adet sayi var."
)

Bu yaklaşım bizi ancak bir yere kadar idare eder tabii. Alt tablo içindeki tüm kareleri gezdiği ve üstüne üstlük set'e koyduğu için bu karelerin sayısı çok büyürse -örneğin 100 milyar- program oldukça yavaş çalışır, C++ bile kurtarmaz. Yine de mesela 1000 x 1000'lik bir alt tablonun üstesinden rahatça gelir.

E, daha iyisi mi var?

Evet ama bir kısıtlamayla: Satır sayısı az olmalı. Satır yerine sütun sayısı da az olabilir, ne de olsa dikey bir alt tablonun her zaman yatay bir eş alt tablosu var. Satırlar ve sütunlar yer değiştirebiliyor yani. Dolayısıyla genelliği bozmadan satır sayısı üzerinden gidebiliriz.

Bu kısıtlama yüzünden aslında satır sayısı da sütun sayısı da büyükse ilk çözüm çok daha avantajlı olacaktır ancak şimdi üzerinde duracağımız çözüm, satır sayısının azlığını harika bir fırsata çevirecek, öyle ki performansı sütun sayısından etkilenmeyecek. Belki sezmiş olabilirsiniz: Matematiksel formüller sayesinde mümkün oluyor bu.

Kod yazmaya başlamadan önce biraz matematikçe konuşmamız ve gözlem yapmamız gerekecek.
(Tekrar gözden geçirirken burada "biraz" dediğimi gördüm. "Biraz"dan çok daha fazlası oldu...)

Adım adım...

Tek satır

Tek satır varken cevap tabii ki sütun sayısı olur çünkü bir satırdaki tüm sayılar farklıdır.

İki satır

Tüm sayıları bir alalım: 2 * sütun sayısı. Şimdi, bunu direkt cevap olarak alamayız çünkü iki satırda da bulunan sayılar olabilir. (Olmayabilir de tabii.)

En baştaki tablomuza tekrar bir bakalım:

Ele alacağımız alt tablo, kırmızı tablonun yalnızca 4. ve 5. satırlarından oluşsun yani alt tablonun da alt tablosu. Bu satırlarda 60 ve 80 sayılarının ortak olduğunu görebilirsiniz, e hâliyle bunları bir yerine iki kere saymış oluruz. Birer kere çıkarmamız lazım. Şu bilgilere sahibiz:

Ortak olabilecek en küçük sayı, ikinci satırın ilk ve en küçük sayısı olan 5 * 9 = 45.
- İkinci satır numarası * ilk sütun numarası
Ortak olabilecek en büyük sayı, ilk satırın son ve en büyük sayısı olan 4 * 20 = 80.
- İlk satır numarası * son sütun numarası
Ortak olan her sayı 4'e de 5'e de bölünebiliyor. İki şartı teke indirgeyebiliriz: 20'ye bölünebiliyor.
- Satırlar ardışık olmasaydı yani aslında ayrık bir tablo olsaydı -örneğin yalnızca 4. ve 6. satırları kapsayan alt tablo- ne olurdu? Sorulması faydalı bir soru çünkü 20'yi aslında direkt satır numaralarının çarpımından elde etmiyoruz. Satırlar ardışık olunca çarpım oluyor tabii ama bu sayı aslında en küçük ortak kat (EKOK). Mesela satır numaraları 4 ve 6 olsa EKOK 12, 21 ve 28 olsa EKOK 84olacaktı.
  - a ve b sayılarının EKOK'u a * b / EBOB(a, b)'ye eşit.

Bu bilgiler ışığında problem şuna indirgeniyor:

[45, 80] aralığında 20'nin katı olan kaç sayı vardır?
- [1, a] aralığında k'nin katı olan floor(a / k) adet sayı vardır (a / k'nin tam sayı kısmı). Buna adet(a, k) diyelim.
- [a, b] aralığında k'nin katı olan sayıların adedi, adet(b, k) - adet(a - 1, k) olur.
Cevap adet(80, 20) - adet(44, 20) = 2olur. Ortak sayıların neler olduğu değil kaç adet olduğu umurumuzda.
- Sütunlar ardışık olduğundan ve arada eksik sütunlar olmadığından dolayı bu ortak sayıların hepsi tabloda yer alacaktır.

Ortak sayıların adedini bulduğumuz anda bunu tüm sayıların adedinden bir kere çıkarmamız yetiyor: 24 - 2 = 22.

Bu küçük problemi de parametreleştirip cevabı bulan kodu yazalım:

C++:

#include <bits/stdc++.h>

using namespace std;

int main() {
    cout << "Satir numaralari: ";
    int ilk_satir, ikinci_satir;
    cin >> ilk_satir >> ikinci_satir;

    cout << "Ilk ve son sutun numaralari: ";
    int ilk_sutun, son_sutun;
    cin >> ilk_sutun >> son_sutun;

    int toplam_sayi_adedi = 2 * (son_sutun - ilk_sutun + 1);

    int a = ikinci_satir * ilk_sutun; // Ikinci satirin en kucugu
    int b = ilk_satir * son_sutun;    // Ilk satirin en buyugu

    int ekok =
        ilk_satir * ikinci_satir / __gcd(ilk_satir, ikinci_satir);

    // a, b'den buyukse hic ortak sayi yoktur.
    // Formulun sonucu negatif olabilecegi icin boyle yapiyoruz.
    int ortak_sayi_adedi = a <= b ? b / ekok - (a - 1) / ekok : 0;

    cout << toplam_sayi_adedi << " adet sayi icinde toplam "
         << ortak_sayi_adedi << " ortak sayi var ve "
         << toplam_sayi_adedi - ortak_sayi_adedi
         << " farkli sayi var.\n";
}

Python:

from math import gcd

print("Satir numaralari:", end=" ")
ilk_satir, ikinci_satir = map(int, input().split())

print("Ilk ve son sutun numaralari:", end=" ")
ilk_sutun, son_sutun = map(int, input().split())

toplam_sayi_adedi = 2 * (son_sutun - ilk_sutun + 1)

a = ikinci_satir * ilk_sutun
b = ilk_satir * son_sutun

# 3.9 ve sonrasinda lcm diye bir metot da var.
ekok = ilk_satir * ikinci_satir // gcd(ilk_satir, ikinci_satir)

ortak_sayi_adedi = b // ekok - (a - 1) // ekok if a <= b else 0

print(
    f"{toplam_sayi_adedi} adet sayi icinde toplam "
    f" {ortak_sayi_adedi} ortak sayi var ve"
    f" {toplam_sayi_adedi - ortak_sayi_adedi} farkli sayi var."
)

Genelleştirebilmek için şöyle düşünebilmekte yarar var: İki satırlı problemi çözebilmek için tek satırlı problemin çözümünü kullandık (sütun sayısı) ve ardından iki satırdaki ortak sayılar için bir formül bulup formülün sonucunu çıkardık.

Üç satır

Bu sefer tabloyu biraz daha geniş tutalım da bolca ortak sayı olsun, matematiğin işimize yaradığını görelim:

Mavi satırı tek tek elimle yazdım, inanabiliyor musunuz? Pratik yolunu tüm yazıyı bitirdikten sonra göz gezdirirken şimdi gördüm...

4., 5. ve 6. satırlarla 9. ile 48. sütunlar arasını kapsayan alt tabloyu ele aldık.

Öncesinde yaptığımız gibi yine toplam sayı adedini bulalım: 3 * 40 = 120. Yine ortak sayıları hariç tutmamız gerekecek.

Şimdi, burada üç tür sayı var:

Yalnızca bir satırda bulunan sayılar
- Birer kere saydık.
Tam olarak iki satırda bulunan sayılar
- İkişer kere saydık.
Üç satırda birden bulunan sayılar
- Üçer kere saydık.

Her sayıyı tam olarak bir kez saymış olmamız gerekirken 120 için durum bu şekilde. Peki ne yapabiliriz?

Tam olarak iki satırda bulunan sayıların adedini çıkarmak adına her satır ikilisi için iki satırlı problemde kullandığımız formülü kullanabiliriz:

4. ve 5. satırlar için aralık [45, 192] ve EKOK 20, dolayısıyla ortak sayı adedi 192 / 20 - 44 / 20 = 7.
4. ve 6. satırlar için aralık [54, 192] ve EKOK 12, dolayısıyla ortak sayı adedi 192 / 12 - 53 / 12 = 12.
5. ve 6. satırlar için aralık [54, 240] ve EKOK 30, dolayısıyla ortak sayı adedi 240 / 30 - 53 / 30 = 7.

Bunların toplamını 120'den çıkaralım: 120 - 26 = 94. Peki 94 tam olarak neyi temsil ediyor şimdi, cevap bu mu?

Tam olarak iki satırda bulunan sayıları ikişer kere saymıştık, şimdi birer kere saymış olduk. Yine de cevaba ulaşmış değiliz çünkü şimdi de üç satırda birden bulunan sayıları hiç saymamış olduk. Neden mi?

Her bir satırda bulunan sayıları saydığımızda -ki bu 120'ye denk geliyor- üç satırda birden bulunan sayıları 3 kere saymış olduk.
Her bir satır ikilisi için ortak sayıları saymak, üç satırda birden bulunan sayıları bir kez saymaya denk geliyor. Nedeni şu ki üç satırda birden bulunan her bir sayı, her zaman herhangi iki satırın ortak bir sayısı olur. Toplamda 3 farklı satır ikilisi olduğundan üç satırda birden bulunan sayıları yine 3 kere saymış olduk.

Bundan dolayı üç satırda birden bulunan sayıların adedini tekrar hesaba katmalıyız. Evet, burada da iki satırlı probleme benzer bir formül gerekecek ama ne hoş ki mantık çok benzer:

Ortak olabilecek en küçük sayı, üçüncü yani son satırın ilk ve en küçük sayısı olan 6 * 9 = 54.
- Son satır numarası * ilk sütun numarası
Ortak olabilecek en büyük sayı, ilk satırın son ve en büyük sayısı olan 4 * 48 = 192.
- İlk satır numarası * son sütun numarası
Ortak olan her sayı 4'e de 5'e de 6'ya da bölünebiliyor. Bunların EKOK'u 60.

Dolayısıyla üç satırda birden bulunan sayıların adedi 192 / 60 - 53 / 60 = 3 olur: 60, 120, 180. Bunu 94'e eklersek 94 + 3 = 97 cevabında her sayı birer kez sayılmış olur.

Bu problemin de kodunu yazmadan geçmeyelim:

C++:

#include <bits/stdc++.h>

using namespace std;

int ekok(int a, int b) { return a * b / __gcd(a, b); }

// Genellestirelim :)
int satirlardaki_ortaklar(const vector<int> &satirlar, int ilk_sutun,
                          int son_sutun) {
    int a = satirlar.back() * ilk_sutun;
    int b = satirlar.front() * son_sutun;

    if (a > b) {
        return 0;
    }

    int tum_ekok = 1;
    for (int satir : satirlar)
        tum_ekok = tum_ekok * satir / __gcd(tum_ekok, satir);

    return b / tum_ekok - (a - 1) / tum_ekok;
}

int main() {
    // Girdilerin sirali verildigini varsayalim, kodu uzatmaya gerek
    // olmasin.

    cout << "Satir numaralari: ";
    vector<int> satirlar(3);
    for (int &no : satirlar)
        cin >> no;

    cout << "Ilk ve son sutun numaralari: ";
    int ilk_sutun, son_sutun;
    cin >> ilk_sutun >> son_sutun;

    int toplam_sayi_adedi = 3 * (son_sutun - ilk_sutun + 1);

    int farkli_sayi_adedi = toplam_sayi_adedi;

    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 3; j++) {
            farkli_sayi_adedi -= satirlardaki_ortaklar(
                {satirlar[i], satirlar[j]}, ilk_sutun, son_sutun);
        }
    }

    farkli_sayi_adedi +=
        satirlardaki_ortaklar(satirlar, ilk_sutun, son_sutun);

    cout << toplam_sayi_adedi << " adet sayi icinde toplam "
         << farkli_sayi_adedi << " farkli sayi var.\n";
}

Python:

from math import gcd
from typing import List


def satirlardaki_ortaklar(
    satirlar: List[int], ilk_sutun: int, son_sutun: int
) -> int:
    a = satirlar[-1] * ilk_sutun
    b = satirlar[0] * son_sutun

    if a > b:
        return 0

    # Hazir lcm metodunu kullanmadan hesaplayalim.
    tum_ekok = 1
    for satir in satirlar:
        tum_ekok = tum_ekok * satir // gcd(tum_ekok, satir)

    return b // tum_ekok - (a - 1) // tum_ekok


print("Satir numaralari:", end=" ")
satirlar = list(map(int, input().split()))

print("Ilk ve son sutun numaralari:", end=" ")
ilk_sutun, son_sutun = map(int, input().split())

toplam_sayi_adedi = 3 * (son_sutun - ilk_sutun + 1)

farkli_sayi_adedi = toplam_sayi_adedi

for i, ilk_satir in enumerate(satirlar):
    for ikinci_satir in satirlar[i + 1 :]:
        farkli_sayi_adedi -= satirlardaki_ortaklar(
            [ilk_satir, ikinci_satir], ilk_sutun, son_sutun
        )

farkli_sayi_adedi += satirlardaki_ortaklar(
    satirlar, ilk_sutun, son_sutun
)

print(
    f"{toplam_sayi_adedi} adet sayi icinde toplam "
    f" {farkli_sayi_adedi} farkli sayi var."
)

Tek satırlı problemin cevaplarını birer kere ekledik, iki satırlı problemin cevaplarını birer kere çıkardık ve üç satır için olan formülün sonucunu bir kere ekledik. Örüntüyü görebiliyor musunuz?

Dört satır

Şimdi sıra yavaş yavaş çözümün değişken satır sayısı için genel hâlini irdelemeye geldi. Bu sefer ortak sayıların teker teker işaretlendiği bir tabloya gerek yoktur herhalde çünkü işimiz formüllerle ve çıkarımlarla artık.

Dört satır olarak 6., 7., 8. ve 9. satırları ele alalım. İlk ve son sütunlar yine 9. ve 48. sütunlar olsun.

Tek satır için olan cevapları toplayalım yani tüm sayıların adedini alalım: 4 * 40 = 160.
Tam olarak iki satırda bulunan sayıları ikişer kere saydık. Birer kere çıkaralım: 160 - 40 = 120. İşlem kalabalıklığı olmasın diye hesaplayıp yazdım.
- Aslında 40, tam olarak değil en az iki satırda bulunan sayıların adedini temsil ediyor. Yine de tam olarak iki satırda bulunanların adedini çıkarmak için buna muhtacız. Sonrasında üç ve dört satırda bulunanlarla ilgileneceğiz zaten.
Tam olarak üç satırda bulunan sayıları C(3, 1) - C(3, 2) kere saydık yani sıfır. Birer kere ekleyelim: 120 + 6 = 126.
- C, kombinasyonun sembolü. Üç satırda bulunanları, tek satırda bulunanları eklerken C(3, 1) kere ekledik ve iki satırda bulunanları çıkarırken C(3, 2) kere çıkardık. Yavaştan bu notasyona geçmek istedim.
Tam olarak dört satırda bulunanları C(4, 1) - C(4, 2) + C(4, 3)kere saydık yani iki kere. Bir tane sayı bile dört satırda birden bulunmadığı için burada işlem yapmıyoruz. Formülün sonucu da sıfır geliyor zaten.
- Tek satırda bulunanları eklerken C(4, 1) kere,
- İki satırda bulunanları çıkarırken -C(4, 2) kere,
- Üç satırda bulunanları eklerken C(4, 3) kere ekledik.

Cevap da 126 olmuş oluyor.

Bunun kodunu paylaşmayayım, üşendim. : D Artık sahne genel çözüm kodunda.

Genelleştirme vakti

Satır sayısı n olsun.

Başta hiçbir sayıyı saymadığımız için tam olarak tek satırda bulunanları saymak adına en az bir satırda bulunanları -tüm sayılar- sayıyoruz.
- Bizim elimizde "en az" formülü var çünkü. "Tam"ı elde etmek için "en az"ları kullanıyoruz.
Tam olarak iki satırda bulunanları bir önceki adımda C(2, 1) kere saydık. Birer kere çıkarmak için en az iki satırda bulunanların sayısını çıkarıyoruz.
Tam olarak üç satırda bulunanları ilk adımda C(3, 1), ikinci adımda -C(3, 2) kere saydık yani C(3, 1) - C(3, 2) = 0. Birer kere eklemek için en az üç satırda bulunanların sayısını ekliyoruz.
Tam olarak dört satırda bulunanları ilk adımda C(4, 1), ikinci adımda -C(4, 2) ve üçüncü adımda C(4, 3) kere saydık: C(4, 1) - C(4, 2) + C(4, 3) = 2. Birer kere çıkarmak için en az dört satırda bulunanların sayısını çıkarıyoruz.
Tam olarak beş satırda bulunanlar için sayımların toplamı C(5, 1) - C(5, 2) + C(5, 3) - C(5, 4) = 0 oluyor ve bundan dolayı en az beş satırda bulunanların sayısını ekliyoruz.

Genelleyelim:

Tam olarak n satırda bulunanlar, önceki adımlarda toplamda C(n, 1) - C(n, 2) + C(n, 3) - ... +/- C(n, n - 1)kere sayılıyor.
- Bu ifadenin çıktığı noktaya tekrar değineyim. Tam olarak n satırda bulunan sayılardan herhangi birini ele alalım: x. Bu sayının bulunduğu nsatırı düşünelim.
  - En az bir satırda bulunanları eklerken n satırdan her birine uğruyoruz ve dolayısıyla x'i C(n, 1) kere sayıyoruz.
  - En az iki satırda bulunanları çıkarırken n satır dahilindeki tüm satır ikililerini ele alıyoruz ve dolayısıyla x'i -C(n, 2) kere sayıyoruz.
  - En az üç satırda bulunanları eklerken n satır dahilindeki tüm satır üçlülerini ele alıyoruz ve dolayısıyla x'i C(n, 3) kere sayıyoruz.
  - Bu şekilde n - 1'e kadar gidiyoruz.
(1 - 1)^n ifadesinin yani sıfırın binom açılımı -C(n, 0) + C(n, 1) - C(n, 2) + C(n, 3) - ... +/- C(n, n - 1) +/- C(n, n). Son terimin işareti n çift ise -, tek ise +oluyor. Sayım ifadesinde sadece ilk ve son terimler eksik.
- n tek ise C(n, 1) - C(n, 2) + C(n, 3) - ... - C(n, n - 1) = (1 - 1)^n + C(n, 0) - C(n, n) = 0,
- n çift ise C(n, 1) - C(n, 2) + C(n, 3) - ... + C(n, n - 1) = (1 - 1)^n + C(n, 0) + C(n, n) = 2 oluyor.
İşte bu yüzden tek adımlarda ekleme (0'dan 1'e) ve çift adımlarda çıkarma (2'den 1'e) yapıyoruz.

Adı belli

Artık bu yöntemin meşhur ismine değinme zamanı: İçerme - Dışlama veya İngilizcede Inclusion - Exclusion. Bu yöntem, saymada bu problemdeki gibi çokça işe yarıyor. Yönteme aşina olmakta yarar var.

Yönteme ve ismine bunca zamandır değinmememin sebebi, adım adım ve yavaş yavaş ilerleyip mantığı kavramanızı istememdi. Önemli olan arkada yatan mantık. Bu sayede yöntemi kavramak rahatlaşıyor.

Kod vakti!

Çözümün tüm detaylarına değindiğimize göre artık şu hızlı programın kodunu bir görelim. Sürprizbozandaki ekran görüntülerini Python'dan almıştım çünkü büyük sayılarla hâlihazırda işlem yapabiliyor, o yüzden ilk Python'u paylaşıyorum:

Python:

import time
from math import gcd


def farkli_sayi_adedi(ilk_satir: int, son_satir: int, ilk_sutun: int, son_sutun: int) -> int:
    def recursive(su_anki_satir, ekok=1, katsayi=-1, eldeki_ilk_satir=0, eldeki_son_satir=0) -> int:
        if su_anki_satir == son_satir + 1:
            if not eldeki_ilk_satir:
                return 0

            a = eldeki_son_satir * ilk_sutun
            b = eldeki_ilk_satir * son_sutun

            return 0 if a > b else katsayi * (b // ekok - (a - 1) // ekok)

        alma = recursive(su_anki_satir + 1, ekok, katsayi, eldeki_ilk_satir, eldeki_son_satir)

        ekok = ekok * su_anki_satir // gcd(ekok, su_anki_satir)
        eldeki_ilk_satir = su_anki_satir if not eldeki_ilk_satir else eldeki_ilk_satir
        al = recursive(su_anki_satir + 1, ekok, -katsayi, eldeki_ilk_satir, su_anki_satir)

        return alma + al

    return recursive(ilk_satir)


print("Ilk ve son satir numaralari:", end=" ")
ilk_satir, son_satir = map(int, input().split())

print("Ilk ve son sutun numaralari:", end=" ")
ilk_sutun, son_sutun = map(int, input().split())

start = time.time()
ans = farkli_sayi_adedi(ilk_satir, son_satir, ilk_sutun, son_sutun)
end = time.time()

print(f"\n{ans} farkli sayi var.\n{(end - start):.2f} saniyede buldu.")

C++ versiyonu, performans avantajından dolayı birkaç ek satırın daha üstesinden gelebiliyor:

C++:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll farkli_sayi_adedi(ll ilk_satir, ll son_satir, ll ilk_sutun, ll son_sutun, ll su_anki_satir = 0, ll ekok = 1,
                     int katsayi = -1, ll eldeki_ilk_satir = 0, ll eldeki_son_satir = 0) {
    if (!su_anki_satir)
        su_anki_satir = ilk_satir;

    if (su_anki_satir == son_satir + 1) {
        if (!eldeki_ilk_satir)
            return 0;

        ll a = eldeki_son_satir * ilk_sutun;
        ll b = eldeki_ilk_satir * son_sutun;

        if (a > b)
            return 0;

        return katsayi * (b / ekok - (a - 1) / ekok);
    }

    ll alma = farkli_sayi_adedi(ilk_satir, son_satir, ilk_sutun, son_sutun, su_anki_satir + 1, ekok, katsayi,
                                eldeki_ilk_satir, eldeki_son_satir);

    ekok = ekok / __gcd(ekok, su_anki_satir) * su_anki_satir;
    if (!eldeki_ilk_satir)
        eldeki_ilk_satir = su_anki_satir;
    ll al = farkli_sayi_adedi(ilk_satir, son_satir, ilk_sutun, son_sutun, su_anki_satir + 1, ekok, -katsayi,
                              eldeki_ilk_satir, su_anki_satir);

    return al + alma;
}

int main() {
    cout << "Ilk ve son satir numaralari: ";
    ll ilk_satir, son_satir;
    cin >> ilk_satir >> son_satir;

    cout << "Ilk ve son sutun numaralari: ";
    ll ilk_sutun, son_sutun;
    cin >> ilk_sutun >> son_sutun;

    auto start = chrono::steady_clock::now();
    ll ans = farkli_sayi_adedi(ilk_satir, son_satir, ilk_sutun, son_sutun);
    auto end = chrono::steady_clock::now();

    auto sure = chrono::duration_cast<chrono::milliseconds>(end - start).count();

    cout << "\n" << ans << "\nfarkli sayi var.\n" << fixed << setprecision(2) << sure / 1000. << " saniyede buldu.\n";
}

Cevabı bulan farkli_sayi_adedi metodu, tüm farklı satır kombinasyonlarını gezip kombinasyondaki satır sayısının teklik-çiftliğine göre ortak sayıların adedini cevaba ekliyor veya cevaptan çıkarıyor. Bu, katsayi argümanı sayesinde mümkün oluyor. Ne zaman kombinasyona satır eklenirse katsayi işaret değiştiriyor.

Toplamda 2^n adet satır kombinasyonu olduğu için program, satır sayısı 20 civarından daha büyük olmaya başladığı an oldukça yavaşlıyor. Eklenen her satır, programı 2 kat yavaşlatıyor.

Ufak bir not

Satırlar ardışık olmak zorunda değil ama ben rahat olsun diye böyle anlattım ve kodladım. Satır sayısı az olsa yeterli. Hadi, bunu da siz kodlayıverin. Oldukça az değişiklik gerektiriyor olmalı.

Bu kadarcıktı

Yazıyı olabildiğince erken tamamlayabilmek için sabahladım ama olsun, çözmekten ve anlatmaktan oldukça zevk aldığım bir problemdi. Anlattıkça ben de çözümü daha iyi kavradım hatta çözümümün ilk hâli birazcık daha anlaşılmazdı.

Bir sonraki aşamada, en başta paylaştığım asıl problemin çözümüne değinirim belki. Bu kadar detaya inmiş olmam umarım sıkmamıştır.

Her zamanki gibi okuduğunuz için teşekkürler ve...

İyi Sosyaller!

Genişletmek için tıkla...

Rehber Çarpım tablosundaki farklı sayıların adedi üzerine

Detaylar

Konu Başlıkları Gizle

Problem ne?

Çözüm?

E, daha iyisi mi var?

Adım adım...

Tek satır

İki satır

Üç satır

Dört satır

Genelleştirme vakti

Adı belli

Kod vakti!

Ufak bir not

Bu kadarcıktı

İyi Sosyaller!

1151

Uzman

Benzer konular

Yeni konular

Yeni mesajlar

Rehber Çarpım tablosundaki farklı sayıların adedi üzerine

Konu Başlıkları Gizle

Problem ne?​

Çözüm?​

E, daha iyisi mi var?​

Adım adım...​

Tek satır​

İki satır​

Üç satır​

Dört satır​

Genelleştirme vakti​

Adı belli​

Kod vakti!​

Ufak bir not​

Bu kadarcıktı​

İyi Sosyaller! ​

1151

Uzman

Benzer konular

Yeni konular

Yeni mesajlar

Problem ne?

Çözüm?

E, daha iyisi mi var?

Adım adım...

Tek satır

İki satır

Üç satır

Dört satır

Genelleştirme vakti

Adı belli

Kod vakti!

Ufak bir not

Bu kadarcıktı

İyi Sosyaller!