Soru

[Bartu Durak]

C dilini kullanarak yazmak istediğim bir program var. Nereden başlayacağımı, nasıl bir algoritma kullanacağımı bilemedim. Foruma danışmak istedim.

Programın yapmasını istediğim şey aslında dart oyununun bitirilmesiyle ilgili bir hesaplama. Hepimizin bildiği dart oyununda tahtada 1'den 20'ye kadar sayılar, bunların iki ve üç katlarıyla birlikte bir de tahtanın ortasında 25 ve onun iki katı olan 50 sayıları bulunuyor; dartınızın isabet ettiği bölgenin puanını alıyorsunuz. 501'den başlayan puanlamada puanını sıfırlayan ilk oyuncu maçı kazanıyor. Her oyuncu sırayla üçer dart atıyor.

Puanınızı sıfırlayacağınız dartın hesaplamasında bitiyor olay. Herhangi bir sayıyı vurup bitiremiyorsunuz; son dart double'lardan olmalı. Örneğin; 32 puanda kaldıysanız D16 ile bitirmelisiniz. Dolayısıyla son dart'a en yakın 50'de geliyorsunuz (D25). Son üç darta ise en yakın 170'te geliyorsunuz (T20, T20, D25).

Yazmak istediğim programın ilgileneceği kısım 170 puanın altı. Kullanıcı programa 170'in altında bir sayı girecek, ve son üç dart kombinasyonunu çıktı olarak alacak.

Örneğin;
Girdi: 128,   Çıktı: T20, T16, D10.
Girdi: 97,     Çıktı: T19, D20.

Tabii ki ikinci örnekteki gibi puanımızı en az atışta sıfırlamak istiyoruz. Bu da yazmakta sıkıntı çektiğim bir konu. 97'yi üç atışta sıfırlamak için çok fazla kombinasyon var; ancak ben örnekteki gibi en az (iki) atışta bitirebileceğim kombinasyonu öğrenmek istiyorum.

Zorlandığım diğer bir konu ise 170'ten küçük sayıyı hızlı bir şekilde, en az dart atarak 50'nin altına düşürebilmek; en yakın double olan D25'e (bull) atarak oyunu bitirebilmek için.

Programı bitirdiğimde daha ileri şeyler için düşüneceğim. Örneğin 24 sayısını atmak istediğimizde T8 değil de D12 kullanmak gibi, double alanları triple alanlarından daha büyük olduğu için dartı isabet ettirmek daha kolay.

Nasıl düşünmeliyim, neler yapılabilir?

[Ozan Arkan Can]

Knapsack Problem - Dynamic Programming belki yardımcı olur

[Hasan Murat]

En son knapsack olarak degerlendirip optimizasyona girelim ki cozumlerinin ve problemin dogasini anla.Brute force bile yer. Ben senin yerinde olsam once brute force dener sonra kendim bir algoritma yazmaya calisirdim. Yaz bir seyler bakalim sonra.

[Bartu Durak]

"Knapsack problem" işime yarar gibiydi ancak bir türlü kendime uyarlayamadım; ya da koda aktaramadım diyelim. Kendim bir şeyler yazmaya çalıştım. 1-170 arasını farklı aralıklara böldüm, her aralıkta hesaplama farklı oluyor. Aralıkları da tabii en az dart atışına ve en kolay atılacak yerlere göre böldüm. Kodun içinde milyonlarca if-else var ancak anlaşılıyor gibi, hepsi bir aralığı belirtiyor. Girdiğimiz değer negatif olunca ise bir önceki sayıdan düşüp yeni sayıya göre işlem yapıyor. İstediğim gibi çalışıyor. Paylaşayım.

Kod: [Seç]

#include <stdio.h>
#include <stdlib.h>

int number;
int previous_number;

int first_dart;
int second_dart;
int final_dart;

int needed;

void calculation()
{
        if(number > 170 || (number < 2 && number >= 0))
        {
                printf("Can not finish!\n\n");
        }
        else
        {
                if(number <= 40 || number == 50)
                {
                        if(number % 2 == 0)
                        {
                                final_dart = number/2;
                                printf("D%d\n\n", final_dart);
                        }
                        else
                        {
                                final_dart = (number - 1)/2;
                                printf("1, D%d\n\n", final_dart);
                        }
                }
                else if((number >= 41 && number <= 60) || number == 65)
                {
                        needed = number - 40;
                        first_dart = needed;
                        final_dart = 20;
                        printf("%d, D%d\n\n", first_dart, final_dart);
                }
                else if(number >= 61 && number <= 70)
                {
                        needed = number - 50;
                        first_dart = needed;
                        final_dart = 25;
                        printf("%d, D%d\n\n", first_dart, final_dart);
                }
                else if(number >= 71 && number <= 100)
                {
                        if((number - 40) % 2 == 1)
                        {
                                if(number == 99)
                                {
                                        printf("D20, 19, D20\n\n");
                                }
                                else
                                {
                                        needed = (number - 57)/2;
                                        first_dart = 19;
                                        final_dart = needed;
                                        printf("T%d, D%d\n\n", first_dart, final_dart);
                                }
                        }
                        else
                        {
                                if(number >= 72 && number <= 80)
                                {
                                        needed = (number - 40)/2;
                                        first_dart = needed;
                                        final_dart = 20;
                                        printf("D%d, D%d\n\n", first_dart, final_dart);
                                }
                                else
                                {
                                        needed = (number - 60)/2;
                                        first_dart = 20;
                                        final_dart = needed;
                                        printf("T%d, D%d\n\n", first_dart, final_dart);
                                }
                        }
                }
                else if(number >= 101 && number <= 120)
                {
                        if((number - 102) % 3 == 0 || (number - 103) % 3 == 0)
                        {
                                first_dart = 20;
                                second_dart = (number - 100);
                                final_dart = 20;
                                printf("T%d, %d, D%d\n\n", first_dart, second_dart, final_dart);
                        }
                        else
                        {
                                if(number >= 101 && number <= 110)
                                {
                                        needed = (number - 50)/3;
                                        first_dart = needed;
                                        final_dart = 25;
                                        printf("T%d, D%d\n\n", first_dart, final_dart);
                                }
                                else
                                {
                                        needed = number - 100;
                                        first_dart = 20;
                                        second_dart = needed;
                                        final_dart = 20;
                                        printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                                }
                        }
                }
                else if(number >= 121 && number <= 150)
                {
                        if(number % 3 == 0)
                        {
                                needed = (number - 30)/3;
                                first_dart = 20;
                                second_dart = needed - 20;
                                final_dart = 15;
                                printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                        }
                        else if(number % 3 == 1)
                        {
                                needed = (number - 40)/3;
                                first_dart = 20;
                                second_dart = needed - 20;
                                final_dart = 20;
                                printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                        }
                        else
                        {
                                needed = (number - 50)/3;
                                first_dart = 20;
                                second_dart = needed - 20;
                                final_dart = 25;
                                printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                        }
                }
                else if(number > 150)
                {
                        if(number < 160)
                        {
                                if((number - 150)%3 == 0)
                                {
                                        printf("Can not finish!\n\n");
                                }
                                else if((number - 150)%3 == 1)
                                {
                                        needed = (number - 40)/3;
                                        first_dart = 20;
                                        second_dart = needed - 20;
                                        final_dart = 20;
                                        printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                                }
                                else
                                {
                                        needed = (number - 50)/3;
                                        first_dart = 20;
                                        second_dart = needed - 20;
                                        final_dart = 25;
                                        printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                                }
                        }
                        else
                        {
                                if((number - 160) % 3 == 1)
                                {
                                        needed = (number - 50)/3;
                                        first_dart = 20;
                                        second_dart = needed - 20;
                                        final_dart = 25;
                                        printf("T%d, T%d, D%d\n\n", first_dart, second_dart, final_dart);
                                }
                                else
                                {
                                        printf("Can not finish!\n\n");
                                }
                        }
                }
        }

}

int main()
{
        while(1)
        {
                printf("Number: \n");
                scanf("%d", &number);
               
                if(number < 0)
                {
                        number = previous_number + number;
                        calculation();
                }
                else
                {
                        calculation();
                }
                previous_number = number;
        }
}

[Hasan Murat]

Eline sağlık. Çözüm kümesini incelemen bence hala çok daha değerli.