Video 002 - Palestra de Pieter Levels

Neste video Pieter Levels fala um pouco de sua experiencia como desenvolvedor. Mesmo sem saber muito de programação, Pieter pos como meta fazer 12 startups em 12 meses. Assim, criou alguns "Minimal Viables Products" que lhe deram retorno financeiro enquanto ele aprendia a programar. Acredito que é muito interesse ouvir o que ele tem a dizer.

Video 001 - Bom final de semana programadores!

Agitado, não?

Resolução da Dinamica 003

Eis um dos possíveis códigos que implementam o algoritmo de Fisher-Yates em C. Acredito que esse ficou bem legalzinho :D

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

int main(){
    int n, m, i, aux;

    srand(time(NULL));

    scanf("%d", &n);
    int vetor[n];

    printf("VETOR ORDENADO: ");
    for(i = 1; i <= n; i++){
        vetor[i - 1] = i;
        printf("%d ", vetor[i -1]);

    }
    printf("\n");
    m = n - 1;

    while(m){
        i = rand() % m;
        aux = vetor[i];
        vetor[i] = vetor[m];
        vetor[m] = aux;
        m--;
    }
    printf("VETOR EMBARALHADO: ");
    for(i = 0; i < n; i++){
        printf("%d ", vetor[i]);
    }
    return 0;

}

Dinamica 003 - Embaralhamento de um vetor

Em muitas aulas os alunos de programação tiveram que aprender algoritmos de ordenação. Porém poucos lugares se dedicam a fazer o contrario: algortimos de embaralhamento. Devido isso, muitos programas usam algoritmos ruins quando precisam embaralhar alguma coisa, como alguns jogos.

Nesta dinamica, vamos implementar o algoritmo de Fisher-Yates, um dos mais simples e eficientes para esta tarefa, para desordenar um vetor de inteiros.

O algoritmo é bom, mas desse jeito é mais estiloso

Etapa 1

Crie uma rotina que, ao usuário entrar com um número N, gere um vetor V de  1 até N. Por exemplo, se N = 8, V = [1, 2, 3, 4, 5, 6, 7, 8] . Isso já foi feito na Dinamica 001.
 
Etapa 2

Gere um número aleatorio K de 0 até N - 1 e faça a troca do último elemento do vetor V para a posição K, e o elemento da posição K para a última posição.
Por exemplo, se V = [1, 2, 3, 4] e K = 1, após a rotina será V = [1, 4, 3, 2]
 
Etapa 3

Coloque a troca feita na etapa anterior numa estrutura de repetição, e decremente a posição do último vetor, para que a troca seja feita e todos os elementos do vetor.
Por exemplo, se N = 5, V = [1, 2, 3, 4, 5].
No passo 1, se K = 2 V = [1, 2, 5,4, 3]
No passo 2, se K = 0, V =  [4, 2, 5, 1, 3]
e assim por diante


Etapa 4 

Finalmente crie o programa completo em C que una as etapas anteriores. Lembre-se de imprimir na tela o vetor original e o embaralhado.

 

Resolução da Dinamica 002

O código que eu desenvolvi para fatorar um número em fatores primos segue abaixo. Como disse no post anterior muitas melhorias podem ser feitas, como por exemplo usar o Teorema de Miller para acelerar a verificação da primariedade dos números.

#include <stdio.h>


int verificaPrimo(int n){
    int i;
    if(n < 2){
        return 0;
    }
    else if(n == 2){
   
        return 1;
   
    }
    else{
     
        for(i = 2; i < n; i+=1){
            if(!(n % i))
                return 0;
            }
        return 1;

        }




    }





int n_esimo_primo(int n){

if( n == 1)
    return 2;

if (n == 2)
    return 3;



int i = 2;


while(n){
  if(verificaPrimo(i)){
        n--;
  }


 
    i+=1;
}
  return i - 1;

 }
int main(){
    int n, i, d;
    scanf("%d", &n);
    i = 1;
     while( n != 1){

        d = n_esimo_primo(i);
        while(!(n % d)){
            printf("%d ", d);
            n = n / d;
        }
        i++;
       
    

    }
}

Dinamica 002 - Fatoração em números primos

Segundo o Teorema Fundamental da Aritmética, todo número maior que 1 pode ser decomposto em um produto de números primos. O problema desta dinâmica é criar um programa que, dado um valor N entrado pelo usuário, este seja fatorado em números primos e estes números sejam impressos na tela.

"Dizia eu que a aritmética... "

Para ajudar a resolução do problema, divide-se o desenvolvimento do programa em 5 etapas:

Etapa 1

Crie uma função, dado um valor X, verifica-se se X é um numero primo.
Por exemplo, se o usuário entra com o valor X = 3, deve-se retornar 1, pois 3 é primo. Se o usuário entra com o valor X = 4, deve-se retornar 0, por 4 não é primo.

Etapa 2

Utilizando a primeira função, crie outra que retorna, dado o valor i, o i-ésimo numero primo, lembrando que 1 não é primo.
Por exemplo, se o usuário entra com o valor i = 1, deve-se retornar 2, pois o primeiro numero primo é 2. Se o usuário entrar com o valor i = 7, deve-se retornar 13, pois o sétimo numero primo é 13.

Etapa 3

Na função principal, crie uma rotina que divide o numero N entrado pelo usuário por 2 e atribui o resultado em N, até que N não seja mais divisivel por 2.
Por exemplo, se o usuário entra com o número N = 60, deve-se divide por 2 e atribuir o resultado em N ficando 30, em seguida, repete-se a divisão até que N = 15. Como 15 não é divisível por 2, neste momento para-se as divisões.

Etapa 4

Modifique a rotina criada na etapa anterior, colocando outra estrutura de repetição que incrementa P, de modo que quando N deixar de ser divisivel por P, P torna-se o próximo numero primo. Lembrando que P deve começar por 2, já que 2 é primo.
Por exemplo, quando N = 60, divide-se por 2 até que N = 15. Depois divide-se por 3 até que N = 5, e depois por 5 até que N = 1.

Etapa 5

Finalmente elabore um programa em C que resolva o problema enunciado ao topo.



Provavelmente o programa feito nessas etapas não será o mais eficiente possível para se resolver o problema, mas acredito que o processo ficou bem didático. Melhorias no código podem ser feitas depois.

Resolução da Dinamica 001

Um dos possíveis códigos que resolvem o problema é esse:

#include <stdio.h>

int main()
{

// primeira etapa

    int n, i, j, achou;
    scanf("%d", &n);
    int v1[n];
    

    for(i = 1; i <= n; i++){
        v1[i - 1] = i;
        printf("%d ", v1[i - 1]);
    }
    printf("\n"); 

// segunda etapa

   int v2[n - 3];
    for(i = 0; i < n - 3; i++){
        scanf("%d", &v2[i]);
       
    }

  


     // terceira etapa

for(i = 0; i < n; i++){
        achou = 0;
        for(j = 0; j < n -3; j++){
            if(v1[i] == v2[j])
                achou = 1;
           
        }
        if(!achou){
            printf("%d ", v1[i]);
        }
       
    }
   
   
    return 0;
}