domingo, 16 de junho de 2013

Resposta do problema da caixa


Programa 7 - Volume da caixa em C
  1. #include <stdio.h>

  2. // Programa que procura o volume máximo de uma caixa, restrito à uma dada área superficial..

  3. int main(){
  4.            int c=0,a=0;
  5. //"c" é o limite de iterações do While da linha 28; a é o auxiliar para diminuir o tempo de busca.

  6.            float area=0,x=0,y=0,z=0,v=0,vs=0,xs=0,ys=0,zs=0;
  7. // "area" é o valor que irá ser digitado. As variáveis x,y,z,v irão ser usadas na busca da solução. As variáveis xs,ys,zs,vs  irão armazenar o valor das melhores soluções.
  8.            
  9.            srand(time(NULL)); // Faz o rand() gerar valores distintos a cada execução.
  10.            
  11.            printf("Digite o valor da area superficial da caixa.\n");
  12.            scanf ("%f",&area);
  13.            
  14.            //area = 255,45; // Para testar a capacidade de achar uma solução ótima, define-se um valor arbitrário e executa o programa n vezes
  15.            
  16.            if(area<=1){a=1;}
  17.            if(area<=10){a=10;}
  18.            if(area<=100){a=100;}
  19.            if(area<=1000){a=1000;} // Otimizando o gasto computacional
  20.            if(area<=10000){a=10000;}
  21.            if(area<=100000){a=100000;}

  22.            while(c<1000){ // Quanto maior o limite de c, maior o gasto computacional, porém melhor é o resultado.
  23.                           x=rand()%a;
  24.                           y=rand()%a;
  25.               
  26.                           while(x>area){x=rand()%a;} // "a" reduz o tempo de busca pois limita a busca a valores próximos do esperado..
  27.                           while (2*x*y>area){y=rand()%a;}
  28.                           z=( (area/2)-(x*y) )/(x+y);  // Lembrar que Área superficial = 2(xy+xz+yz)
  29.               
  30.                           v=x*y*z; // Cálculo do volume..
  31.                           if(v>vs){vs=v;xs=x;ys=y;zs=z;} // Se a solução é melhor, substitui valores..
  32.                           c++;
  33.                          }// Fim While
  34.               
  35.            printf ("\n\nVolume maximo: %f \n\nAs medidas sao x=%.2f\ty=%.2f\tz=%.2f\n\n",vs,xs,ys,zs);
  36. //Nessa linha, o código %.2f ordena imprimir até as 2 primeiras casa decimais do resultado.
  37.            
  38.            system("pause");
  39.            }// Fim Main

       Nesse programa é interessante observar a tática usada para diminuir o tempo de busca do computador. Nas linhas 19 até 24, "a" é determinado de acordo com cada área superficial dada. Ou seja, quando nas linhas 27 e 28 efetua-se  x=rand()%a e  y=rand()%a obtemos valores menores que a área superficial, e ainda, provavelmente mais próximos da solução ideal. Lembrar que esse programa é aleatório. Se você executá-lo várias vezes, poderá obter resultados diferentes, entretanto satisfatórios em sua maioria. Esse é o princípio da busca aleatória, que é feita em programas de otimização.

       Novamente vemos as linhas rand () e srand(time(NULL)). Ambas são funções e fazem parte da biblioteca padrão de C. A linha rand() gera um número randômico qualquer. A linha srand(time(NULL)) faz com que esse número seja diferente a cada execução do programa, pois estabelece uma relação com o relógio do computador.

       Bem, por hoje é só. No próximo post, alguns exercícios de C, do estilo dos que eu fiz quando fazia a disciplina de algoritmos no IFET, e que podem cair em provas. Para quem está fazendo a disciplina, é uma boa.

Boa semana à todos!

quarta-feira, 12 de junho de 2013

Estruturas de repetição (2)

       Boa noite! Hoje o post é a continuação das estruturas de repetição. Vou falar do "For infinito", do While e aproveitando o gancho, sobre o conceito de programação estocástica (aleatória). Esse tipo de programação consiste na aproximação do resultado ideal, por uma busca aleatória. No final um desafio, que devo postar a resposta em breve...Vou considerar o For infinito uma extrapolação do uso convencional do for convencional. Lembrando, o for convencional tem a seguinte forma : For(inicialização;limite;incremento){Comandos;} . O For infinito pode se dar de algumas formas: 

                       
For( ; ; ){Comandos;}

                       For(inicialização ; ;){Comandos;
                       
For(; ; incremento){Comandos;}

                       For(inicialização ; ; incremento){Comandos;}

       Note: no primeiro caso, nada se estabelece para o For, ou seja, ele irá executar o comando indefinidamente, até que alguma condição seja atendida e o loop seja encerrado, ou até o programa "dar pau". Digo isso, pois não conheço a fundo as implicações desse uso do For, podem haver erros inesperados em sua execução. Já o segundo tipo, possui um início e um padrão de crescimento/decrescimento, porém não possui um limite.

       Para sair de um For infinito, como eu já mencionei, é preciso impor uma condição de saída, com um comando que encerre o loop. Veja a seguir:

Trecho 1
  1. int i;
  2. for(;;){

  3.           i++;
  4.           if(i>50)break; // Condição e comando de saída 
  5.           printf("%d",i);
  6.           
  7.          }
Trecho 2
  1. int i;
  2. for(i;;){

  3.           i++;
  4.           if(i>50)break; // Condição e comando de saída 
  5.           printf("%d",i);
  6.           
  7.          }
Trecho 3
  1. int i;
  2. for(;;i++){

  3.           if(i>50)break; // Condição e comando de saída 
  4.           printf("%d",i);
  5.           
  6.          }
Trecho 4
  1. int i;
  2. for(i;;i++){

  3.           if(i>50)break; // Condição e comando de saída 
  4.           printf("%d",i);
  5.           
  6.          }
      Como você imagina as saídas desses programas? São iguais? A resposta é não. Os trechos 1 e 2 irão fazer uma contagem de 1 a 50, enquanto que os trechos 3 e 4 de 0 a 50.
      
      Quanto ao While: seu uso, como eu disse no post Estruturas de repetição (1), é para algo que você sabe onde irá acabar, ou ao menos para que se atinja um valor esperado. Imagine o seguinte: você tem um problema muito grande de Programação Linear (otimização), que te dá milhões de possibilidades de soluções. Logo, para percorrer todo o cenário de respostas possíveis, o tempo de operação do computador é muito grande, acredite.

      O que você faz? Faz o que chamamos de busca aleatória. Você escolhe pontos por onde procurar a solução, e, por exemplo, com o uso do While, estabelece um pré valor esperado para sua solução, por exemplo Lucro = 5000 Reais. Feito isso, a primeira solução que o programa encontrar que te dê R$ 5000 ou mais de lucro, ele apresenta à você. A ideia é simples assim. Entretanto sua aplicação nem tanto. Conheço vários professores  e alunos daqui da UFJF, que estudam esse estilo de programação, tanto em C,C++,Matlab,etc... é um assunto interessante que irei retomar em um próximo post.

      Basicamente o While se dá assim: While(Condição){Comandos;}. Veja:

Programa 6 - Busca aleatória do lucro em C.
  1. #include <stdio.h>

  2. int main () {

  3. int lucro=0,x=0,y=0,contador=0;
  4. srand(time(NULL)); // Essa linha é responsável pelo rand() abaixo, gerar números diferentes a cada execução.
  5. while(lucro<5000){
  6.                            contador++; // Número de iterações.
  7.                            x=rand(); // x = Número aleatório.
  8.                            x=x%1000; // x = Resto da divisão de x por 1000.
  9.                            y=rand(); // y = Número aleatório.
  10.                            y=y%1000; // y = Resto da divisão de y por 1000.
  11.                            lucro = 2*x + 4*y; // Função Objetivo
  12.                           }
  13. printf("\n\nx=%d\n\ny=%d\n\nLucro=%d\n\nIteracoes=%d\n\n",x,y,lucro,contador);

  14.          
  15. system("pause");
  16. return(0); }
Observações: 

      Nesse post, inseri alguns comandos ( rand e srand ) que você podia não conhecer. São comandos da biblioteca padrão de C. Não se preocupe muito com a forma com que eles funcionam por enquanto, só saiba que eles funcionam e são de grande valia na programação. Num próximo post, irei abordar detalhes destes.

      Também apresentei uma parte do conceito de programação estocástica. Esse é um tema vasto, com inúmeras aplicações reais em problemas da matemática, engenharia, estatística e de empresas. Vários softwares já foram desenvolvidos com base nesse conceito e ainda rola muita pesquisa em universidades à respeito disso. É outro assunto que voltarei a falar numa próxima oportunidade. É uma boa pra se informar.


Proposta: Mexa no Programa 6. Rode várias vezes e observe as variações de solução. Mude as condições, e a equação objetivo do problema. Dificulte o trabalho do programa para achar a solução. Tente algo para que o número de iterações aumente bastante. Tente algo para que o número de iterações caia bastante também. Isso pode ser feito mexendo nas linhas 10 e 12, mudando o divisor da divisão, aumentando o lucro,etc...

Desafio: Esse eu considero realmente um desafio. Não se preocupe se não conseguir. 


Programa 7 - Volume da caixa em C.

Dada uma determinada caixa, de dimensões X, Y e Z;
sua área superficial é descrita por 2(XY+XZ+YZ).
Proposta: Com base em um valor qualquer de área superficial,encontrar o 
máximo volume que pode ser obtido e quais as dimensões da caixa de maior volume.
Ou seja, maximizar a capacidade da caixa, com menos material gasto...

Obs: Faça para áreas superficiais de até 100.000 unidades.

Boa semana à todos!

domingo, 2 de junho de 2013

Resposta do problema de programação linear


Programa 5 - Otimização Barcos
  1.  #include <stdio.h>
  2. int main(){
  3.     
  4.     int a,b,c,l=0,ra,rb,rc,rl=0;// a = jangadas, b = canoas , c = arcas
  5.     
  6.     for (a=0;a<5;a++){
  7.          for (b=0;b<9;b++){
  8.                 for (c=0;c<4;c++){
  9.                           if (a+b+c<11){ // restringe o máximo de capitães
  10.                           if(a+2*b+3*c<19){ // restringe o máximo de funcionários
  11.                                   l=(50*a)+(70*b)+(100*c); if(l>rl){ rl=l ; ra = a; rb = b ; rc = c;}
  12. // Faz o teste, se o lucro encontrado na equação é maior que o lucro armazenado, se sim troca as respostas para arcas, canoas, jangadas e lucro.
  13. // As variáveis que começam com r estão armazenando a resposta.
  14.                                 } 
  15.                                                  }
  16.                                              }
  17.                                         }
  18.                                    }
  19.     
  20.     printf ("Solucao: \n\nJangadas = %d\nCanoas = %d\nArcas = %d\nLucro = %d\n\n\n",ra,rb,rc,rl);
  21.     system("pause");
  22.     return 0;
  23.            }    

sexta-feira, 31 de maio de 2013

Estruturas de repetição (1)


       Olá! Boa noite! Hoje darei início aos posts abordando também as estruturas de repetição. Elas podem ser o For(para), While (Enquanto) e Do-While(Faça-Enquanto). Basicamente a diferença entre o For e as estruturas While, é que o primeiro é geralmente usado para problemas em que se sabe quantas iterações (repetições) serão realizadas, e que a realização dessas não depende de outra condição inicial. Já as estruturas While são usadas para quando se quer uma contagem indefinida, por exemplo procurar uma solução de equação ou problema de Programação Linear*. Ou seja, quando uma solução é encontrada o While pára automaticamente.

       As estruturas tem as seguintes "caras":
              
              For(Inicialização;Limite;Incremento){Comandos;}
          
              While(Condição){Comandos;}

              Do{Comandos;}While(Condiçao);

       Há ainda a diferença entre While e Do-While que é o seguinte: o While só executa se a condição for atendida. O Do-While executa pelo menos uma vez, ainda que sua condição não esteja satisfeita, e então, se for este o caso, pára. Ou seja:


Programa 2: While e Do-While em C

  1.               #include<stdio.h>
  2.               
  3.               int main(){

  4.                                int i=6;

  5.                                while(i==2){
  6.                                                    i=i*3;
  7.                                                    printf("\n\n%d\n\n",i);
  8.                                                   }//Este loop nunca irá rodar

  9.                                do{
  10.                                       i=i*5;
  11.                                       printf("\n\n%d\n\n",i);
  12.                                      }while(i==2); // Este loop será executado e trará resposta 30 na tela.
  13.                                
  14.                                system("pause");
  15.                                return 0;
  16.                               
  17.                               }

      Entretanto, pensei esse post para falar mais do For, na sequência lançar outros sobre While/Do-While e mais tarde mais aplicações dos três...
    O For, como já foi dito, tem a seguinte "cara": For(Inicialização;Limite;Incremento){Comandos;}. A inicialização, é de onde partirá a "contagem", o limite é até onde ela vai, e o incremento de qual valore ela vai ser acrescida ou decrescida a cada repetição. Imagine o seguinte, um algoritmo que diga para subir uma escada de 30 degraus, um a um. Logo, você parte do primeiro degrau ( 0 ), chega ao último degrau (29) e sobe de um em um (i++). Seria algo mais ou menos assim:

Programa 3: For básico em C
  1.               #include<stdio.h>
  2.               
  3.               int main(){

  4.                                int i=0;

  5.                                for(i=0;i<30;i++){//(Inicialização;Limite;Incremento)
  6.                                                              printf("\n\n%d\n\n",i);
  7.                                                             }//Este loop executa 30 passos, do 0 ao 29.

  8.                                
  9.                                system("pause");
  10.                                return 0;
  11.                               
  12.                               }
    Note que o a variável de repetição, i, na linguagem C tem que ser declarada antes da estrutura For. Também é bom notar que o limite imposto NUNCA é atingido. Por exemplo, se o limite é 30, os loops vão até i = 29! Parece óbvio, pois olhando o sinal, o limite é menor que 30. Entretanto essa é uma característica do For que pode trazer resultados errados ao seu programa, se você se esquecer dela. 
      Há também o For usado com decremento, ou seja diminuindo. Imagine agora, que você quer descer a mesma escada que acabou de subir, o programa fica quase igual, exceto pela linha 7:

      7.                                for(i=30;i>0;i--){//(Inicialização;Limite;Incremento)

    Nesse For, o i começa de fato em 30, decresce um a um, chega em 1 e pára. É o chamado For Backward (de trás pra frente). O anterior é o For Foward.
      Na maior parte das vezes, usa-se o for para contagens, para adicionar dados a algum problema, para realizar testes nos programas, etc... A seguir um exemplo simples:

Programa 4: Fatorial com For em C
  1.               #include<stdio.h>
  2.               
  3.               int main(){

  4.                                int i=0,s=1;

  5.                                for(i=1;i<11;i++){//(Inicialização;Limite;Incremento)
  6.                                                            s*=i; // A cada repetição, s é multiplicada por i.
  7.                                                             }//Este loop executa 10 passos, do 1 ao 10.

  8.                                printf("\n\n%d\n\n",i);//Saída 3628800

  9.                                
  10.                                system("pause");
  11.                                return 0;
  12.                               
  13.                               }
Observações:

    Programação Linear é uma área da otimização, que utiliza uma função objetivo, e restrições lineares. Ou seja, problemas do tipo maximizar lucro de uma fábrica que possui "x" funcionários e precisa produzir "y".
    
    Os sinais "++","--" são alternativos para "i=i+1" e "i=i-1". Já " s*=i " é o mesmo que " s=s*i ". Isso funciona da mesma forma para " s+=i ", " s-=i "...

    A seguir alguns bons livros sobre C/C++:

      Introdução à programação. 500 Algoritmos resolvidos. Por Anita Lopes e Guto Garcia.
      Guia C++ para Iniciantes por Herbet Schildt.
      C Completo e Total por Herbert Schildt.

Proposta: Tente, usando o For, resolver o seguinte problema de Programação Linear.

    A Capitão Caverna S.A., localizada em Pedra Lascada, aluga 3 tipos de barcos para passeios marítimos: jangadas, super-canoas e arcas com cabine. A companhia fornece juntamente com o barco um capitão para navegá-lo e uma tripulação que varia de acordo com a embarcação: uma para jangadas, duas para super-canoas e três para arcas. 
    A companhia tem 4 jangadas, 8 super-canoas e 3 arcas; e em seu corpo de funcionários: 10 capitães e 18 tripulantes.
    O aluguel é por diárias e a Capitão Caverna lucra $50 por jangada, $70 por super-canoa e $100 por arca.

    Objetivo: Maximizar o lucro obedecendo as restrições impostas.
(Resposta 4 jangadas, 4 super-canoas, 2 arcas, lucro $ 680)
Solução: Programa 5 - Barcos Otimização


Bom fim de semana à todos!

terça-feira, 28 de maio de 2013

Um pouco sobre C/C++, Linhas Condicionais.

       Bom dia! Me chamo Rodrigo. Atualmente sou estudante de Engenharia Elétrica da UFJF, tendo começado o curso de    engenharia no IFET-Sudeste.. De agora em diante serei colaborador do blog e vou postar alguns tópicos de estudo sobre C, C++, posteriormente aplicações nas áreas de modelagem computacional (basicamente a implementação de problemas reais), curiosidades, desafios... Enfim, será uma série para estudos das linguagens C, C++ e sobre aplicações práticas da programação.
       Pra quem precise aprender para a faculdade é uma boa, pra quem gosta ou tem bolsa de pesquisa mais ainda. É uma área muito visada no meio da engenharia, pois muito da pesquisa que se faz em universidades se passa pela simulação computacional...
       Não farei aqui algum tipo de apostila ( pois na internet já existem várias), o que farei são postagens com programas já feitos e algumas discussões sobre seu funcionamento. Para iniciar (seguir) seus estudos, já foi recomendado aqui, o material do Prof. Jabour disponível em Apostila, na aba Ensino, é uma boa pedida pra quem nunca viu C... Também há vários bons livros sobre C e C++, que no próximo post irei recomendar aqui. Podem fazer perguntas e sugestões à vontade nos comentários!



Programa 1: Soma e Subtração básica em C



  1. #include <stdio.h>// biblioteca padrão em C

  2. int main ( ) {
  3.                   int a, b, soma, final; // Declaração das variáveis

  4.                   printf("\n Digite um valor:\n"); // Comando de impressão na tela

  5.                   scanf ("%d",&a); // Lê o que o usuário digitou no teclado

  6.                   printf("\n Digite um segundo valor:\n");

  7.                   scanf ("%d",&b);

  8.                   soma = a+b; // Soma os valores a e b e atribui o resultado à variável soma.

  9.                   if (soma>20) {
  10.                                          final = soma+8; } // Comando condicional
  11.     
  12.                   else {
  13.                            final = soma-5; } // Complemento do comando condicional
  14.                   
  15.                   printf ("\n O resultado e: %d", final);

  16.          
  17.                   system("pause") // Linha de comando para que se possa visualizar o resultado na tela
  18.                   return 0; } // Retorno da função main( )




       Bem, esse é um programa bem simples de ser entendido, mesmo por quem ainda está começando. São 26 linhas de código, o que é bem pouco. Na linha 1 temos a inclusão da biblioteca stdio.h, que faz parte da biblioteca padrão de C. Biblioteca é, basicamente, um conjunto de funções. Na linha 3 temos a declaração da função main ( ), que deve estar em qualquer programa em C. Por ela se dá a execução do código. Em seguida dois pares printf/scanf que servem para pedir que o usuário digite um valor e em seguida armazenam esse valor em variáveis int. Na linha 14 faz-se a soma dos valores que o usuário digitou. Logo vem o mais interessante desse programa, as linhas condicionais. Na linha 16 temos : Se a soma for maior que 20 faça isto ( soma + 8). Na sequência, na linha 19 temos o complemento: Senão faça isto (soma - 5). Ou seja, se a soma de 'a' e 'b' for menor ou igual a 20 ( note que a condição é >20) ele subtrai 5 e, somente se, for maior que 20 ele soma 8. O resultado é impresso e o código retorna 0 para main ( ).

Observações:
     
       //As linhas verdes, precedidas por // são apenas comentários! Não interferem no código e são muito úteis em qualquer programa... Lembre-se de que há programas complexos e extensos, e sem comentários é praticamente impossível entender seu funcionamento.

       Atente para a identação do código. Ou seja, os espaços antes de cada comando. O que pertence ao if, à frente do if, o que pertence ao else, à frente do else...

       A linha 25 serve somente para que a tela "congele" ao mostrar o resultado. É uma maneira de fazer isso, apesar de haver controversas, nunca tive problemas com ela. Mais adiante postarei uma alternativa.

       A linha 26 dá o retorno da função main ( ). É recomendado dar algum retorno para toda função que não seja do tipo void ( que não possui retorno ).

Proposta:

       Modifique o programa bastante. Mude as operações, faça com produtos( * ), divisões( / ), etc... Inclua printf para que mostre o resultado da operação antes de entrar nas linhas condicionais ( essa é uma ótima maneira de testar programas que dão errado, e achar o erro!), mude o else da linha 19 por outro if, e tente obter o mesmo resultado...

Boa semana à todos!