kolokwium11_12_zad1.cpp

/*
  1. Mamy tablicę [1..max,1..max]. Napisz funkcję, która zwraca długość najdłuższego podciągu 
  rosnącego znajdującego się w dowolnym (jednym) wierszu, którego wszystkie elementy są ze sobą 
  względnie pierwsze.
*/
#include<cstdio>
#include<algorithm>

using namespace std;

#define MAX 3

bool coprime(int a, int b) {
  for(int i=2;i*i<=max(a,b);i+=2) {
    if(a%i==0 and b%i == 0) return false;
  }
  return true;
}

int longest_ascending_coprime_subset_row(int row[], int nrow) {
  int longest = 0;
  int tmpstart = 0;

  for(int i=1;i<=nrow;i++) {
    bool ok=true;
    if(i != nrow and row[i-1] < row[i]) {
      bool allcoprime = true;
      for(int j=tmpstart;j<i;j++) {
        allcoprime = coprime(row[j],row[i]) and allcoprime;
      }
      if(allcoprime) {

      } else {
        ok = false;
      }
    } else {
      ok = false;
    }
    if(!ok) {
      longest = max(longest,i-tmpstart);
      tmpstart = i;
    }
  }
  return longest;
}

int longest_ascending_coprime_subset(int tab[MAX][MAX], int ntab) {
  int longest = 0;
  for(int i=0;i<ntab;i++) {
    longest=max(longest,longest_ascending_coprime_subset_row(tab[i],ntab));
  }
  return longest;
}

int main() {

  int tab[MAX][MAX]={ {3,2,1},{9,8,7},{2,4,7} };

  printf("%d\n", longest_ascending_coprime_subset(tab,MAX));

  return 0;
}

kolokwium11_12_zad3.cpp

/*
  3.Mamy cykliczną listę zawierającą liczby całkowite. Każda pierwsza cyfra kolejnej liczby jest równa
  ostatniej cyfrze poprzedniej liczby.
  np. 123 - 324 - 435 - 578 -> łańcuch się zapętla
  Napisz funkcję wstawiającą liczbę do listy. Liczba ma zastąpić dwie już istniejące elementy cyklu.
  dla przykładu tutaj, za (324 - 435) można wstawić 35
  Funkcja powinna zwrócić wartość logiczną w zależności od tego czy próba wstawiania zakończyła się
  sukcesem.
*/
// Zakładam, że łańcuch nie zachowuje swojej właściwości z ostatnią i pierwszą cyfrą na zapętelniu

#include<cstdio>

using namespace std;

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

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 = chain->next;
  chain = chain->next;
}

void show_chain(node* chain) {
  node* start = chain;
  bool first = true;
  while(chain != start or first) {
    first = false;
    printf("%d ",chain->val);
    chain = chain->next;
  }
  printf("\n");
}

int first_digit(int a) {
  while(a>=10) {
    a/=10;
  }
  return a;
}

int last_digit(int a) {
  return a%10;
}

bool insert(node *chain, int a) {
  if(chain == NULL) return false;
  node* start = chain;
  node* prev = start;
  node* cur = start->next;
  node* tmp;
  while(cur != start) {
    if((first_digit(prev->val) == first_digit(a)) and (last_digit(a) == last_digit(cur->val))) {
      prev->val = a;
      tmp = cur->next;
      delete cur;
      prev->next = tmp;
      return true;
    }
    prev = cur;
    cur = cur->next;
  }

  return false;
}

int main() {
  int tab1[] = {123,324,435,578};
  node *chain;
  make_chain(chain,tab1,4);
  show_chain(chain);
  printf("success: %d\n",insert(chain,35));
  show_chain(chain);
  return 0;
}