Kolokwium zaliczeniowe WDI 2009/2010

kolokwium9_10_zad1.cpp

/*Zad. 1 Dana jest duża tablica typu tab=array[1..n] of integer. Proszę napisać funkcję, która 
zwraca informację, czy w tablicy zachodzi następujący warunek: „wszystkie elementy, których 
indeks jest elementem ciągu Fibonacciego są liczbami złożonymi, a wśród pozostałych 
przynajmniej jedna jest liczbą pierwszą”. 
Uwagi: 
• Czas na rozwiązanie zadania wynosi 25 minut, za zadanie można otrzymać 5 punktów. 
• Oceniane będą: przejrzystość i czytelność kodu oraz efektywność rozwiązania.*/
#include<cstdio>

using namespace std;

bool is_prime(int a) {
  for(int i=2;i*i<=a;i+=2) {
    if(a%i==0) {
      return false;
    }  
  }
  return true;
}

bool condition_is_true(int tab[],int n) { //(tablica, rozmiar tablicy)
  int fprev, fcur, ftmp; //ciag fibonnaciego
  fprev=1;
  fcur=1;
  bool cond1 = true; //wszystkie z indeksem z ciagu fibonnaciego sa zlozone
  bool cond2 = false; //wsrod pozostalych przynajmniej jedna jest pierwsza
  for(int i=0;i<n;i++) {
    if(i==fcur) { //element o indeksie z ciagu fibonnaciego
      cond1 = !is_prime(tab[i]) and cond1;
      //ciag fibonnaciego
      ftmp = fcur;
      fcur = fprev+fcur;
      fprev = ftmp;
    } else {
      cond2 = is_prime(tab[i]) or cond2;
    }
    //printf("tab[i]:%d cond1:%d cond2:%d is_prime(tab[i]): %d\n",tab[i],cond1,cond2,is_prime(tab[i]));
    if(!cond1) return false;
  }
  return cond1 and cond2;
}

int main() {
  //1,2,3,5,8
  int tab1[9] = 
  //0,1, 2, 3,4,5,6,7,8
  { 10,32,12,4,8,8,3,7,8 };
  printf("%d\n",condition_is_true(tab1,9));
  return 0;
}

kolokwium9_10_zad2.cpp

/*Zad. 2 Dany jest zbiór n liczb naturalnych umieszczony w tablicy typu tab=array[1..n] of integer. 
Proszę napisać funkcję, która zwraca informację, czy jest możliwy podział zbioru n liczb na trzy 
podzbiory, tak aby w każdym podzbiorze, łączna liczba jedynek użyta do zapisu elementów tego 
podzbioru w systemie dwójkowym była jednakowa. Na przykład: 
{2,3,5,7,15} -> true, bo podzbiory {2,7} {3,5} {15} wymagają użycia 4 jedynek, 
{5,7,15} -> false, podział nie istnieje. 
Uwagi: 
• Zawartość tablicy wejściowej nie może ulec zmianie. 
• Czas na rozwiązanie zadania wynosi 25 minut, za zadanie można otrzymać 5 punktów. 
• Oceniane będą: przejrzystość i czytelność kodu oraz efektywność rozwiązania. 
• Dodatkowe 2 pkt. można otrzymać, jeżeli funkcja zamiast informacji logicznej, w efektywny 
sposób policzy i zwróci liczbę istotnie różnych podziałów zbioru na podzbiory. Na przykład: 
{2,3,5,7,11,15} -> 2, bo {2,15} {3,7} {5,11} albo {2,15} {3,11} {5,7}*/
#include<cstdio>
#define MAX 6
using namespace std;

int count_ones(int a) {
  int ones = 0;
  while(a>0) {
    if(a%2==1) ones++;
    a/=2;
  }
  return ones;
}

int count_ones_in_tab(int tab[], int ntab) {
  int ones = 0;
  for(int i=0;i<ntab;i++) {
    ones+=count_ones(tab[i]);
  }
  return ones;
}

int subsets_inner(int tab[], int ntab, int ss1[], int nss1, int ss2[], int nss2, int ss3[], int nss3) {
  if(ntab == 0) { //nie ma juz liczb w tablicy
    if((count_ones_in_tab(ss1,nss1)==count_ones_in_tab(ss2,nss2))&&(count_ones_in_tab(ss2,nss2)==count_ones_in_tab(ss3,nss3)))
      return 1;
    else
      return 0;
  }
  ss1[nss1] = tab[ntab-1];
  int css1 = subsets_inner(tab,ntab-1,ss1,nss1+1,ss2,nss2,ss3,nss3);
  ss2[nss2] = tab[ntab-1];
  int css2 = subsets_inner(tab,ntab-1,ss1,nss1,ss2,nss2+1,ss3,nss3);
  ss3[nss3] = tab[ntab-1];
  int css3 = subsets_inner(tab,ntab-1,ss1,nss1,ss2,nss2,ss3,nss3+1);

  return css1+css2+css3;
}

int subsets(int tab[],int ntab) {
  int ss1[MAX],ss2[MAX],ss3[MAX];
  return subsets_inner(tab,ntab,ss1,0,ss2,0,ss3,0)/6; // dzielimy przez 3!
}

int main() {

  int tab[MAX] = { 2,3,5,7,11,15 };
  printf("%d\n",subsets(tab,MAX));

  return 0;
}

kolokwium9_10_zad3.cpp

/*Zad. 3 Dany jest łańcuch zbudowany w oparciu o elementy typu:
pnode = ^ node;
node = record
val : integer;
next : pnode;
end;
Kolejne elementy łańcucha o zwiększającej się wartości pola val nazywamy podłańcuchem 
rosnącym. Proszę napisać procedurę, która usuwa z łańcucha wejściowego najdłuższy podłańcuch 
rosnący. Warunkiem usunięcia jest istnienie w łańcuchu dokładnie jednego najdłuższego 
podłańcucha rosnącego.
Uwagi:
• Czas na rozwiązanie zadania wynosi 25 minut, za zadanie można otrzymać 5 punktów.
• Oceniane będą: przejrzystość i czytelność kodu oraz efektywność rozwiązania.*/
#include<cstdio>

using namespace std;

struct node {
  int val;
  node *next;
  node(int va){val=va; next=NULL;}
};

void show_chain(node* chain) {
  while(chain != NULL) {
    printf("%d ",chain->val);
    chain = chain->next;
  }
  printf("\n");
}

void remove_longest_ascending_subchain(node *&start) {
  if(start == NULL || start->next == NULL) {
    start=NULL;
    return;
  }
  node *warden;
  warden = new node(2e9);
  warden->next = start; 

  node *prev = warden;
  node *current = prev->next;

  int longest = -1;
  bool repeated = false;
  int tmplength = 1;

  node *tmpstart = prev;
  node *savedstart = prev;
  node *savedend = current;

  while(true) {
    if(current and current->val > prev->val) {
      tmplength += 1;
    } else {
      if(tmplength > longest) {
        repeated = false;
        longest = tmplength;
        savedend = current;
        savedstart = tmpstart;
      } else 
      if(tmplength == longest) {
        repeated = true;
      } 
      tmpstart = prev;
      tmplength = 1;
    }
    if(!current) break;
    prev = current;
    current = current->next;

  }
  if(!repeated&&longest>=1) {
    node* tmp=savedstart->next;
    node* tmp2;
    while(tmp!=savedend) {
      tmp2=tmp->next;
      delete tmp;
      tmp=tmp2;
    }
    savedstart->next = savedend;
  }
  start = warden->next;
}

void make_chain(node *&chain, int tab[], int ntab) {
  chain = new node(0);
  node* ac = chain;
  for(int i=0;i<ntab;i++) {
    ac->next = new node(tab[i]);
    ac = ac->next;
  }
  ac->next = NULL;
  chain = chain->next;
}


int main() {
  node *chain;
  int tab[] = {31,21,20,30,50,9,11,13,15};
  make_chain(chain,tab,9);
  show_chain(chain);
  remove_longest_ascending_subchain(chain);
  show_chain(chain);
  printf("\n");
  int tab1[] = {1,2,3,4,50,9,11,13,15};
  make_chain(chain,tab1,9);
  show_chain(chain);
  remove_longest_ascending_subchain(chain);
  show_chain(chain);
  printf("\n");
  int tab2[] = {10,2,3,4,50,56,11,13,15};
  make_chain(chain,tab2,9);
  show_chain(chain);
  remove_longest_ascending_subchain(chain);
  show_chain(chain);
  printf("\n");
  int tab3[] = {10,2,3,4,50,9,11,13,15};
  make_chain(chain,tab3,9);
  show_chain(chain);
  remove_longest_ascending_subchain(chain);
  show_chain(chain);
  return 0;
}