geri

KTÜ Bilgisayar Mühendisliği 3. Bilgisayar Olimpiyatları için hazırladığım soru

17/10/2012

Son 2 yıldır KTÜ Bilgisayar Mühendisliği Bölüm Başkanı Prof.Dr.Vasıf Nabiyev öncülüğünde düzenlenen bilgisayar olimpiyatlarına kurucularından olduğum 4Primes büyük bir gururla sponsor oluyor. Sponsorluğun dışında final yarışması için bir de ödüllü özel soru hazırlıyoruz. 2012 baharında düzenlenen 3. olimpiyatlar için hazırladığım soruyu geç de olsa paylaşmak istedim. Yazının sonunda bir de örnek çözüm yer alıyor.

Olimpiyatlarda bir yarışmacı takım ödüllü sorumuza doğru yanıt vermeyi başardı. Aşağıda verdiğim örnek çözüm gerekenden çok daha fazlasını içeriyor. Doğru yanıt veren takım oldukça sade ve güzel bir çözümle geldi. Bu güzel çözümün karşılığında da ödüllerini aldılar. M. Esat YAŞAYAN, Yasin YILMAZ ve Hakan SÖNMEZ'den oluşan takımı bir kez de buradan tebrik etmek isterim.

Soru

Uzun yıllar önce paralel bir evrende, for ve while döngülerinin yanı sıra dizi(array) kullanımının yasak olduğu, STL kütüphanesinin henüz icat edilmediği günlerde tren yolculukları için gerekli olan kömür miktarını hesaplama görevi bilgisayar bilimcilerine verilmişti. Her yolculuktan önce seyahat edecek yolcu sayısına göre kaç kg kömüre ihtiyaç olduğu hesaplanıyor ve gereken kömür trene yükleniyordu. Hesaplama yapılırken vagon başına gereken kömür miktarları toplanarak trenin toplam kömür ihtiyacı elde ediliyordu. Bir vagon için gereken kömür miktarı, o vagonda seyahat edecek yolcu sayısına eşit ya da küçük ve yolcu sayısı ile aralarında asal olan pozitif tamsayıların sayısına eşitti. Örnek olarak vagonda 9 yolcu var ise 9 ile aralarında asal olan pozitif tamsayılar 1, 2, 4, 5, 7 ve 8 olduğundan bu vagon için 6kg kömür gerekli oluyordu.

Sizden sıradaki tren için girdi.gir dosyasından vagonlardaki yolcu sayılarını okuyarak sırasıyla her bir vagon için gereken kömür miktarı ile tren için gereken toplam kömür miktarını cikti.cik dosyasına kaydeden bir uygulamayı C dilinde yazmanızı istiyoruz.

Kısıtlar

İpuçları

Dosyadan okunacak olan tüm yolcu sayıları asaldır.

Örnek bir girdi.gir dosyası aşağıda verilmiştir.

17 31 37 97 59 107 131 157 113 173

Bu girdiye göre trenin toplam 10 vagonu bulunmakta ve bu vagonlarda sırasıyla 17, 31, 37, 97, 59, 107, 131, 157, 113 ve 173 yolcu oturmaktadır. Bu trenin hareket etmesi için 912kg kömür gerekir. Bu verilere göre cikti.cik dosyası aşağıdaki gibi olur.

16 30 36 96 58 106 130 156 112 172
912

Örnek kod

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

struct list
{
   int head;
   struct list *tail;
};

struct list *map(struct list *l, int (*func)(int))
{
   struct list *n = (struct list *) malloc(sizeof *n);
   n->head = func(l->head);
   if(l->tail == NULL)
   {
       n->tail = NULL;
   }
   else
   {
       n->tail = map(l->tail, func);
   }  
   return n;
}

struct list *filter(struct list *l, int (*func)(int))
{
   if(l == NULL)
   {
       return NULL;
   }
   struct list *n = (struct list *) malloc(sizeof *n);
   if(func(l->head)){
       n->head = l->head;
       n->tail = filter(l->tail, func);
   }
   else
   {
       return filter(l->tail, func);
   }
   return n;
}

int fold(struct list *l, int (*func)(int, int))
{
   if(l->tail != NULL)
   {
       return func(l->head, fold(l->tail, func));
   }
   else
   {
       return func(l->head, 0);
   }
}

void print(struct list *l, FILE *file)
{
   if(l != NULL)
   {
       print(l->tail, file);
       fprintf(file, "%d ", l->head);
   }
}

int phi_func(int element){
   return element - 1;
}

int sum_func(int head, int tail)
{
   return head + tail;
}

struct list *read_file(FILE *file, struct list *l)
{
   int num;
   if(fscanf(file, "%d", &num) > 0)
   {
       struct list *n = (struct list *) malloc(sizeof *n);
       n->head = num;
       n->tail = l;
       return read_file(file, n);
   }
   return l;
}

int main()
{
   FILE *input = fopen ("girdi.gir", "r");
   if ( input != NULL )
   {
       struct list *l = read_file(input, NULL);
       fclose(input);
       l = map(l, phi_func);
       int sum = fold(l, sum_func);
       FILE *output = fopen ("cikti.cik", "w");
       print(l, output);     
       fprintf(output, "\n%d\n", sum);   
       fclose(output);
   }
}


Doğru yanıt veren takımın çözümü

#include <iostream>
#include <fstream>
using namespace std;

//----------------------------------
  struct list
  {
   int sayi;
   int sonuc;
   list *next;
  };
  list *first,*current;
  
  ifstream oku("giris.txt");
  ofstream yaz("cikis.txt");
  int toplam;
//----------------------------------

void okur()
{   
       oku>>current->sayi;

       current->next=new list;
       current->next->next=NULL;
       current=current->next;
     
      if(!oku.eof())
        okur();
      else
        return;
}

void hesapla()   //girisler her zaman asal sayi oldugundan aralarinda asal sayi miktari her zaman 1 eksigidir.
{
     current->sonuc=current->sayi-1;
     
     toplam+=current->sonuc;
     current=current->next;
     
     if(current->next!=NULL)
       hesapla();  
}

void yazar()
{   
     yaz<<current->sonuc<<" ";
     current=current->next;
     
     if(current->next!=NULL)
       yazar();
     else
       return;
}

void basla()            
{
     first=new list;
     first->next=NULL;
     current=first;
           
     okur(); 
     
     current=first;
     toplam=0;
     
     hesapla();
     
     current=first;
     
     yazar();
     
     yaz<<toplam;
     
     oku.close();
     yaz.close();            
}
//-------------------------------------------
main()
{         
  basla();  
  return 0;    
}

Follow me on Twitter