Google Code-in - O altfel de competiție

Google Code-in

Ce este Google Code-in și cine poate participa?

Pe scurt, Google Code-in este un program dedicat elevilor din întreaga lume cu vârste cuprinse între 13 și 17 ani inclusiv, creat de Google sub forma unui parteneriat cu numeroase organizații de tip open-source (anul acesta 25 la număr, printre care și Ubuntu, Drupal, WikiMedia) pentru a încuraja participarea în proiecte și comunități definite de licența liberă. Programul durează aproximativ 50 de zile în fiecare an, anul acesta având loc între 28 noiembrie și 17 ianuarie.

Fie că vrei să codezi (și aici vei găsi probleme de rezolvat în ce limbaj preferi: Python, C++, Java, Javascript și nu numai), fie că vrei să testezi software, fie că vrei să scrii documentație sau doar să înveți mai multe despre lumea open-source, vei găsi ceva la care ți-ar făcea plăcere să lucrezi în cadrul Google Code-in! În plus, vei cunoaște o comunitate minunată, formată atât din elevi, cât și din oameni de profesie, care lucrează la programe și servicii bine cunoscute în lumea IT. Nu ar trebui să îți faci griji cu privirea la dificultatea taskurilor oferite, căci și mentorii și ceilalti paricipanți te vor sprijini să înveți cât mai mult din această experiență.

Cum poți participa? De ce este o „competiție”?

Înscrierea și participarea sunt complet gratuite. Ai nevoie doar de un cont Google și trebuie să te asiguri că te încadrezi în intervalul de vârstă acceptat. Te poți înscrie oricând pe durata programului, nu neapărat la început.

C++: The "strcat" and "strcpy" functions

Today I'm going to introduce you 2 new functions from the "string.h"  library: "strcpy" which copies the content of a string in another one and "strcat"  which concatenates 2 strings.

I can't show you the syntax of these to functions better than with an example, so let's try to solve the following problem: In the input file there are 2 strings, "x" and "y". You have to create a "z" string with the content from the "x" string, followed by the content from the "y" string and between them the word "and". After that, print on the screen the 3 strings

problem.in

apples

pears

problem.out

the x string is apples

the y string is pears

the z string is apples and pears

Here you are the source-code for the problem, using the 2 functions:
#include <string.h>
#include <stdio.h>
int main ()
{
         freopen("problem.in", "r", stdin);
         freopen("problem.out", "w", stdout);
        char x[1000],y[1000],z[1000];
        int i;

        //now we'll read the 2 strings from the input file
        gets(x);
        gets(y);

        //in the next we'll copy the string "x" in the string "z"

C++: Diferente intre Borland C++ si MinGW

Diferentele dintre aceste 2 medii de programare sunt putine la nivel incepator, mediu si nu foarte avansat, insa la nivel profesionist acestea incep sa se inmulteasca. In acest articol, va voi prezenta CELE MAI SEMNIFICATIVE 7 DIFERENTE DINTRE BORLAND C++ SI MINGW, suficiente pentru categoria intai enumerata.

1. Functia principala ("main") nu mai poate fi declarata de tip "void" (ca in Borland), ci doar de tip "int", implicand aparitia randului de comanda "return 0;", la sfarsitul programului.
2. Dupa anumite biblioteci (precum "fstream", "iostream" si "algorithm") mai trebuie introdusa comanda pentru alocare de spatiu: "using namespace std;".
3. ".h" - ul de la finalul tuturor bibliotecilor din Borland dispare in unele cazuri (ex. "fstream" si "iostream"), iar in celelalte cazuri se pastreaza (ex. "math.h" si "stdio.h") si se poate inlocui cu un "c" la inceput, ambele fiind corecte in MinGW (adica se poate scrie "stdio.h" sau "cstdio").
4. Limitele se maresc foarte mult pentru tipurile de declarare a varibilelor, "int" ajungand aproape cat vechiul "long"!!!
5. Programul primeste un "WARNING" daca nu este dat un "Enter" la sfarsitul sursei, astfel incat cursorul mouse-ului sa fie pe randul urmator, ca in imagine:

C++: Ciurul lui Eratostene

Ciurul lui Eratostene este o metoda de verificare a numerelor daca sunt prime, destul de lenta si foarte limitata la matematica, dar cea mai rapida la informatica, in cazul in care se cere verificarea proprietatii de prim pentru mai multe numere. In cazul a mai putin de 10 numere se foloseste algoritmul clasic: Verificarea lui "n" daca este prim (varianta clasica).
TEORIA:

Pasul 1: Cream un sir de numere consecutive (de la 2) pana la maximul posibil precizat in restrictiile problemei.

Pasul 2: Incepem cu primul numar (2) si intr-un sir auxiliar cu exact atatea elemente ca primul (in care initial toate sunt 0) marcam multiplii numarului, prin transformarea in 1 a valorilor corespunzatoare acestora, din al II^lea sir.
Pasul 3: Luam urmatorul numar pentru care valoarea sa din al II^lea sir este 0 si repetam pasul 2 pentru numarul respectiv.
Pasul 4: .......

C++: Descompunerea in factori primi

Descompunerea in factori primi (sau descompunerea canonica) este un algoritm foarte util, chiar unul dintre cei de baza.

Cu ajutorul algoritmului obtinem fiecare factor din descompunere alaturi de puterea la care apare si, in randurile de mai jos, le afisam:

f=2;

while(n!=1){

           p=0;

           while(n%f==0){

                         n/=f;

                         p++;

          }

          if(p!=0)

                    cout<<f<<” “<<p;

          f++;

}

“f” reprezinta factorul, iar “p” puterea.

C++: Functia “sort”, cea mai rapida metoda de sortare a vectorilor

Pana acum cunoastem ca metoda de sortare a vectorilor bubble sort-ul, adica algoritmul cu for in for sau cel cu do while, dar astazi vreau sa va arat o functie care sorteaza vectorii, reprezentand  si cea mai rapida metoda posibila si cea mai scurta din punct de vedere al codului.
Aceasta functie se numeste sort si face parte din biblioteca <algorithm>. Iata-i codul in program pentru cazul ordonarii crescatoare a vectorului “v” cu “n” elemente, care a fost citit incepand cu pozitia 0:

sort(v, v+n);

In cazul in care scrierea in vector se incepe de pe pozitia 1, apelarea functiei va arata astfel:

sort(v+1, v+n+1);

Poate ca acum ma veti intreba cum se realizeaza ordonarea descrescatoare. Ei bine, pentru aceasta mai trebuie definita de catre utilizator urmatoarea functie (pentru a afla cum se defineste o functie vezi articolul: Functii definite de catre utilizator) :

bool  descr(<tip> a, <tip> b)
{

C++: Interclasarea

Avand la dispozitie doua tablouri unidimensionale, adica 2 vectori, cu elemente ordonate (crescator sau descrescator) trebuie sa construim un al 3-lea tablou care sa contina elementele primelor 2, respectand acelasi criteriu de ordonare.

Varianta I, cu un timp de executie ridicat

O prima idee ar fi aceea de a reuni elementele celor 2 vectori intr-un al 3-lea, pe care sa il sortam apoi crescator sau descrescator. Rezultatul obtinut dupa efectuarea acestei metode este, bineinteles, cel asteptat, insa dupa cum stim operatia de sortare este mare consumatoare de timp si de aceea aceasta metoda este ineficienta, avand in vedere faptul ca beneficiem de vectorii A si B gata ordonati.


Algoritmul cel mai rapid pentru problema data se numeste INTERCLASARE si este foarte cunoscut si important, dar nu pentru incepatori (primul an de studiu). Mai jos, dupa urmarirea unei analize pas cu pas (cu imagini si explicatiile aferente acestora) a unui exemplu concret de interclasare pe vectori, pentru a intelege ideea de la baza interclasarii, veti gasi algorimul ce realizeaza procedeul descris.

C++: Rotirea unei matrice cu 90°

Astazi va voi arata un algoritm foarte practic, dar ceva mai avansat si intr-o anumita masura mai interesant decat cele pe care vi le-am prezentat pana acum. Acesta consta in rotirea unei matrice patratice cu 90° in sensul acelor de ceasornic. Aceasta rotire a matricei necesita o matrice auxiliara in care o vom roti pe cea initiala, deoarece nu putem folosi o variabila ajutatoare. O alta varianta ar fi un vector auxiliar, dar astfel algoritmul se complica. Iata mai jos algoritmul de rotire cu 90° in sensul acelor de ceasornic sau spre dreapta a matricei "a" in matricea auxiliara "b":

            for(i=1; i<=n; i++)

                    for(j=1; j<=n; j++)

                           b[i][j]=a[n-j+1][i];

Foarte simplu de retinut, nu-i asa? Dar care este explicatia? Imaginile de mai jos reprezinta matricea initiala "a" si matricea in care aceasta a fost rotita, adica "b", iar cu ajutorul lor vei vedea exact unde "va ajunge" fiecare element dupa efectuarea algoritmului de rotire.

C++: Functii/Subprograme definite de utilizator (teorie si exemple)

    Teorie:

  ->  Functiile sau subprogramele sunt foarte utile in cazul in care aveti de repetat un algoritm de mai multe ori in acelasi program, iar declararea si apelarea lor nu este foarte greu de invatat. Acestea se declara dupa includerea bibliotecilor si inainte de 'main'. 


  -> Iata prototipul unei functii:

<tipul_returnat> numele_functiei(<tip_parametru> param1, <tip_parametru> param2, ...)
{
           <tip> var1, var2, ....;  //declararea variabilelor pe care le vom folosi
           //codul functiei
           return valoare/variabila;
}

  ->  Mai exista si un alt tip de functie, numita procedura, care se executa fara a intoarce nimic . Iata si prototipul acesteia:

void numele_functiei(<tip_parametru> param1, <tip_parametru> param2, ...)
{
           <tip> var1, var2, ....;  //declararea variabilelor pe care le vom folosi
           //codul procedurii
}

    Exemple:

 
   1) Se da de la tastatura un numar natural "n" si se cere sa se scrie un program care afiseaza numarul de cifre ale lui "n", folosind un subprogram:


#include <iostream>
using namespace std;
int cif(int a) 
{
      int cnt=0;

Rezolvarea problemei "talent"

Acum 2 zile am publicat enuntul problemei "talent", data  la ONI 2011 clasei a VI-a si v-am lasat timp sa o rezolvati. Problema a fost destul de interesanta si in algoritmul de rezolvare se ascundeau niste idei de optimizare a timpului de executie esentiale celor ce vroiau sa ia 100 de puncte. Iata mai jos rezolvarea problemei:

#include <fstream>
using namespace std;
ifstream fin("talent.in");
ofstream fout("talent.out");
long sp[15001],dist[15001];
int main ()
{
 long n,nr,cop,x=0,y,i,j,cif[11],imp,cnt,pali,p=1,t,k,max=0, min=2000000001;
 fin>>n;
 for(i=1; i<=n; i++)
 {
  fin>>nr;
  cop=nr;
  cnt=0;
  imp=0;
  for(j=0; j<10; j++)
   cif[j]=0;
  while(cop>0)
  {

Problema "talent", ONI 2011, cls. a VI-a

In acest week-end va fi Olimpiada Nationala de Informatica, la Iasi, si in ultimele saptamani am tot facut probleme din anii trecuti, asa ca m-am gandit sa va arat o problema de ONI. Am ales una mai usoara, anume "talent", care s-a dat anul trecut la clasa a VI-a, la care va las sa va ganditi cateva zile: in urmatoarea saptamana voi posta si rezolvarea..... Acum iata enuntul problemei:

C++: Prima cifra a nr. "n

Un algoritm foarte util si simplu este cel cu ajutorul caruia putem determina prima cifra a lui "n", in cazul in care "n" este un numar intreg, fara a avea cifrele sale intr-un vector sau matrice, situatie in care accesam pur si simplu prima pozitie scrisa a vectorului. Iata acum algoritmul:

                      cn=n;

                      while(cn>9) ...

The ASCII table: The basic for all the programmers

The ASCII code is part from the basics of programming. The ASCII table is a table which contains all the graphic signs as characters with a number corespondent (beetween 0 and 255). This table is usable  and able to be recognized from all the programming languages (C, C++, Java, HTML, PHP, Windows developers etc.) and all the developer programs. See right here down the \ASCII table. Click on it for make it bigger and more readable...

C++: Verificarea lui "n" daca este prim (varianta clasica)

Un alt algoritm important, clasic si util este acela ce verifica daca numarul "n" este un prim. Exista mai multe variante ale "for"-ului dupa "d" din aceasta problema si anume limitarea "d<=n", "d<=n/2" sau "d*d<=n", in ordinea descrescatoare timpului de executie (de la cel mai mare la cel mai mic). Algoritmul pe care vi-l voi prezenta este cel mai scurt de scris si cu un timp foarte rezonabil (cel mai rezonabil dintre cele 3 variante) si este si usor de invatat, totusi e bine de stiut ca mai exista si alti algoritmi ce verifica acest lucru, insa sunt mult mai lungi, mai greoi, dar cu un timp de executie remarcabil mai mic.
Iata algoritmul:
                    
                    prim=1;
                    for(i=2; i<=n/2; i++)  ...

C++: Aflarea lui CMMDC si a lui CMMMC pentru nr. "a" si "b"

In acest post va voi prezenta algoritmul de C++ ce scoate CMMDC si CMMMC pentru 2 numere date, "a" si "b", utilizand doar biblioteca <iostream>.

Pentru CMMDC:

int a,b,cmmdc,ca,cb;

cin>>a>>b;

ca=a; cb=b;

while(ca!=cb)

if(ca>cb) ca-=cb;

else cb-=ca;

cmmdc=ca;

Principiul acestui algoritm este cel mai simplu posibil pentru a afla CMMDC: scadem "a" din "b" sau invers (in functie de care este mai mare) pana ajungem ca acestea sa fie egale => atunci CMMDC egal cu "a" sau cu "b" (deoarece ele sunt egale), iar "ca" si "cb" reprezinta copiile variabilelor "a" si "b", pe care le utilizam cu scopul de a nu strica valorile variabilelor citie initial.

Pentru CMMC (notam cmmdc=cmmdc(a,b) ca fiind algoritmul pentru CMMDC prezentat mai sus):
cmmdc=cmmdc(a,b);
cmmmc=a*b/cmmdc; 

C++: Transformare nr. "n" zecimal in binar

Astazi va voi arata un algoritm de C++ foarte cautat, care transforma numarul "n" zecimal in numar binar (sub forma unui vector) si afiseaza numarul binar, cu alte cuvinte il trece pe "n" din baza 10 in baza 2. Algoritmul este facut in cea mai simpla biblioteca, adica <iostream.h> pentru a putea fi folosit la toate nivelurile de studiu si poate fi folosit atat in Borland C++, cat si in MinGW. Iata acum despre ce va vorbeam:

                            

                            int binar[33], lungime;

                 for(i=1; n>=0; i++)

                 {

                       binar[i]=n%2;

                       n/=2;

                 }

                 lungime=i;

                 for(i=lungime; i>0; i--)           
                        cout<<binar[i]; 

Acesta este algoritmul, acum ... succes la invatat!