Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

 

Arranjos

As linguagens de programação procuram dar suporte à implementaçao do conceito de vetores e matrizes existentes na matemática. Na linguagem C a base deste suporte são os arranjos. Um arranjo é constituído de uma seqüência indexável de variáveis todas do mesmo tipo.

De um ponto de vista mais computacional: podemos dar um único nome a uma região da memória constituida de várias variáveis de um mesmo tipo ao invés de termos que dar um nome distinto a cada variável.

Já vimos como utilizar as variáveis correspondentes aos tipos primitivos. Na linguagem C, além do tipos primitivos T (p.ex. int, double, char) podemos criar um agrupamento (uma coleção, um conjunto etc) que denominamos um “arranjo de T”, p.ex. “arranjo de int”, “arranjo de caracteres”, etc.


Considere um programa, como no caso do cálculo dos dígitos verificadores do CPF, que extrai os dígitos de um número armazenado em uma variável do tipo int. Uma possibilidade de concepção para este programa é a declaração de nove variáveis do tipo int; o trecho de programa abaixo declara nove variáveis e atribui um valor a duas delas:
int d0, d1, d2, d3, d4, d5, d6, d7, d8;
d0=cpf%10;
d1=cpf/10%10;...

Com o uso de arranjos podemos criar um agrupamento que pode conter um número arbitrário de variáveis de um mesmo tipo. No trecho de programa abaixo é declarado um arranjo com nove componentes ou elementos ou variáveis do tipo int e é atribuido o valor de um dígito na base 10 a cada um dos componentes deste arranjo:
int d[9];
d[0]=cpf%10;
d[1]=cpf/10%10;...
No trecho acima d é o nome do "arranjo de ints" (nome das 9 variáveis indexáveis) e d[0] representa um componente ou variável do tipo int (primeiro elemento ou componente) e d[8] corresponde ao último elemento ou componente. A linguagem C não trata o “tipo arranjo” da mesma maneira que trata outros tipos como por exemplo os tipos primitivos. Exceto por uns poucos aspectos podemos dizer que não existe  1 (uma) “variável” com nome “d”, existem 9 (nove) variáveis com nome d[0], d[1], ...d[8]. Além disso observe que definido um arranjo a de tamanho N, independentemente do valor de N o primeiro elemento é a[0]. O último elemento é a[N-1], ou seja os índices correspondem a gama de zero a N-1 (0..N-1). Conforme é visto à frente a[N] (erro!!) corresponde a uma indexação inválida (similarmente a[-1] também é uma indexação inválida, ambas instâncias do (anti-)padrão conhecido em em inglês como “off by one”).

Podemos indexar os elementos de um arranjo de forma similar à notação da matemática. Indexar significa indicar um dos elementos do arranjo utilizando um índice. Os índices em C começam de zero e o operador de indexação consiste em abre e fecha colchetes - []. Assim d[0] denota o primeiro elemento do arranjo.

A linguagem C permite que elementos de qualquer tipo possam se constituir na forma de arranjo. Assim a expressão geral para o tipo "arranjo de <tipo>" é:
"<tipo> <nome>[<tamanho>]"
conforme exemplos abaixo:
int ai[100];
double ad[200];
char ac[300];
float af[25];

Os componentes de um arranjo podem ser iniciados ou inicializados de forma semelhante às variáveis de tipos primitivos com o que parece ser literais do tipo arranjo, utilizamos os inicializadores de arranjo:

O trecho de programa abaixo define e inicializa um arranjo de inteiros e faz uma “pesquisa” neste arranjo para encontrar o valor do menor elemento e também encontra um índice para um dos elementos com menor valor:

    int a[]={70,60,40,30,20,10, 50};
    int ii;
    //encontra o menor elemento
    int menorValor, indMenor;
    menorValor=a[0];
    indMenor=0;
    for(ii=1; ii<7; ii++)
      if(a[indMenor]>a[ii]){
        menorValor=a[ii];
        indMenor=ii;
      }
    printf("Menor:%d, indice:%d\n", menorValor, indMenor);

No trecho de programa acima a identifica um arranjo de 7 variáveis do tipo int (de a[0] até a[6]). O trecho de programa quer determinar o valor e o índice no arranjo com menor valor (no caso 10 e 5 respectivamente). Para isso considera-se primeiramente que o menor valor corresponde ao conteúdo de a[0] e o índice do elemento com menor valor é 0. o comando for itera sobre os elementos do arranjo verificando se algum deles é menor do que o elemento de índice zero. Escreva um programa para encontrar o maior valor (e seu índice) e escreva um programa para encontrar o menor e o maior valor concomitantemente.

O trecho de programa abaixo define e inicializa um arranjo para codificar o número de dias em cada mês do ano.

int numDiasMes[]={0, 31,28,31,30,31,30,31,31, 30, 31, 30, 31};
int totalDias=0;
int i;
for(i=1; i<=12; i++) totalDias+=numDiasMes[i];

O trecho de programa acima declara um agregado do tipo arranjo denominado numDiasMes. Este agregado é iniciado (é iniciada a região de memória onde existem 13 variáveis indexáveis do tipo int). Cada variável int é iniciada com um dos 13 valores mostrados. Cada valor corresponde ao número de dias do mês de índice correspondente. A primeira variável de um arranjo em C corresponde ao índice 0 (zero). Como o primeiro mês, Janeiro, é tradicionalmente denotado pelo número 1, o trecho acima opta por ignorar o primeiro elemento do arranjo - numDiasMes[0]. Isto ilustra um padrão nas linguagens onde a indexação se inicia com o valor 0: para representar uma seqüência 1, 2, 3, ...N podemos usar um arranjode  tamanho N+1 e não utilizar o elemento de índice 0, ou podemos usar um arranjo de tamanho N e ter o cuidado de tratar o elemento de índice i como sendo o (i+1)-ésimo elemento (p.ex. o elemento de índice 1 é o segundo elemento). Este aspecto se generaliza para valores que não são muito distantes do valor 0: se precisamos representar dados de uma seqüência, p.ex. 4, 5, 6, podemos usar um arranjo de tamanho 7 e não utilizar os elementos de índice 0, 1, 2 e 3. Por outro lado podemos usar um arranjo de tamanho 3 e lembrar que o índice 4 da seqüência corresponde ao índice 0 do arranjo.

A linguagem C permite algumas variações sintáticas de iniciação. Uma delas permite explicitarmos os elementos que queremos iniciar:

int ai[4][5]={ [0][0]=10, [0][4]=20, [2][2]=30};

Os iniciadores de arranjo não podem ser utilizados nas expressões dos comandos de atribuição! O trecho de programa abaixo não é compilável:

int numDiasMes[13];
numDiasMes={0, 31,28,31,30,31,30,31,31, 30, 31, 30, 31}; /* erro! */

A linguagem C tem poucas operações que permitem a manipulação do arranjo como um todo.O tratamento usual nas linguagens de programação, e a linguagem C não é exceção, é reservar a memória de forma contígua para cada elemento dos arranjos, com isso um arranjo corresponde a um bloco de memória. Sabendo o endereço de memória correspondente ao início de um arranjo e sabendo o tamanho de cada elemento podemos, de maneira eficaz e eficiente, calcular o endereço e acessar cada um dos elementos de um arranjo. Observe que, uma vez criado um bloco de memória para um arranjo, este bloco não pode ser “esticado” nem “encolhido”. Por outro lado o bloco pode ser criado (nas versões mais modernas da linguagem C) de forma “dinâmica”:

int i;
scanf("%d",&i);
double ad[i];

-------

Na linguagem C o tipo “char []” tem semelhanças com o tipo “char *”

Os arranjos de caracteres têm um papel especial na linguagem C e serão tratados em outra página. Veja por exemplo que eles têm mais de uma possibilidade de inicialização:

char c1[]={'A', 'B', 'C', 0};
char c2[]="ABC";

A linguagem C não dá suporte ao tipo “string” mas utiliza os arranjos de caracteres “para simular” que existe o tipo “string”. Por convenção os arranjos de caracteres na linguagem C correspondem a “strings” e “strings” são arranjos de caracteres que têm como “último caractere”(convencionalmente) o caractere nulo (todos os bits em zero!).

--------

A representação de uma “matriz” na linguagem C pode feita utilizando um arranjo de arranjos. Veja abaixo um exemplo de representação de uma matriz identidade 3x3 utilizando um arranjo de arranjos de ints e utilizando também o mecanismo de inicialização:
int matIdent[3][3]={ {1,0,0}, {0,1,0}, {0,0,1}};

-------

No material sobre variáveis foi comentado que a linguagem C utiliza, por diversas razões, os chamados “ponteiros”. Dado um tipo T podemos sempre definir um tipo que é “ponteiro para T”. Os arranjos não são exceção, na verdade os projetistas da linguagem C definiram os arranjos de forma a fazê-los ficar bem próximos aos ponteiros: existe um relacionamento forte entre arranjos e ponteiros! Qualquer operação de indexação de arranjos pode ser feita com manipulação de ponteiros, em particular a linguagem reforça a equivalência entre as duas formas:
(i) exp1[exp2] e
(ii) *(exp1+exp2)

Nas expressões (i) e (ii) acima devem ser considerados vários aspectos, por exemplo o operador + é um de dois operadores (a)pointer+int ou (b)intt+pointer, o operador de indexação é um de dois operadores (a)pointer[int] ou int[pointer]. A aritmética de ponteiros depende do tipo que o ponteiro aponta: (p+1) equivale a (p+sizeof(T)) onde T é o tipo que p aponta, de forma mais geral (p<op>n) equivale a p<op>n*sizeof(T). Apesar da “equivalência” entre ponteiros e arranjos um identificador de ponteiro corresponde a uma posição de memória mas um identificador de arranjo é somente um “nome” e tem associado a ele um tipo e um valor (constante!) que corresponde ao endereço da primeira posição do arranjo em memória. Falando de outro modo um ponteiro corresponde a um “right-value” e também a um “left-value”, podemos fazer atribuições a um ponteiro. Um identificador de arranjo corresponde a somente um “right-value” (um valor constante) e não pode receber atribuições (no material sobre funções e parâmetros será visto que um parâmetro declarado como “arranjo” “transmuta” em um ponteiro!!).

A declaração

int a[10];

define um arranjo com 10 variáveis: a[0], a[1],...a[9];

A notação a[i] refere-se ao i-ésimo elemento do arranjo. Se pa é um ponteiro para um inteiro declarado como:

int *pa;

então atribuição

pa=&a[0];

ajusta pa para apontar para o elemento de índice 0 de a (primeiro elemento). e a expressão:

*(pa+k)

refere-se ao elemento de índice k  ou (k+1)-ésimo elemento do arranjo a (dizemos que k é o “offset” ou deslocamento). Observe que, conceitualmente, o tipo “ponteiro para int” é diferente do tipo “ponteiro para arranjo de n ints” e isto não está sendo tratado acima.

Quando se mistura o “operador” de indexação (modificador arranjo) com o “operador” de indireção (modificador ponteiro) nas declarações temos que aplicar as regras de prioridade e associação da tabela do material de expressões. Considere a seguinte expressão:

int *id[5];

Sem considerar as questões de prioridade e associatividade haveria pelo menos duas possibilidades de interpretação:
(i) id corresponde a um arranjo de 5 ponteiros para ints, ou
(ii) id corresponde a um ponteiro para um arranjo de 5 ints.
A figura abaixo ilustra as opções:

Pela tabela de prioridades e associatividades da linguagem C podemos observar que o operador de indexação tem prioridade sobre indireção e a interpretação adequada é a primeira: id corresponde a um arranjo de 5 ponteiros para int, se quisermos ter certeza disso basta usar a expressão equivalente int *(id[5]); e observar que é possível indexar id:
int ai[5]={100,200,300,400,500};
int *id[5];
id[0]=&ai[0]; id[1]=&ai[1]; id[2]=&ai[2]; id[3]=&ai[3]; id[4]=&ai[4];
int ii;
for(ii=0; ii<5; ii++) printf(“%d\n”, *id[ii]);

Para obter a interpretação (ii) a expressão correspondente é int (*id)[5]; (ponteiro para arranjos de 5 ints). O uso no caso desta última interpretação é diferente:
int ai[5]={100,200,300,400,500};
int (*id)[5];
id=&ai;
int ii;
for(ii=0; ii<5; ii++) printf(“%d\n”, (*id)[ii]);

Observe que
int (*px)[10];
corresponde a definir que px é um ponteiro para um arranjo de ints (px é do tipo ponteiro para arranjos com 10 ints). Nesta declaração só temos a alocação da variável px, não é alocado o arranjo! Se quisermos alocar dinamicamente um arranjo para px apontar podemos usar a função calloc, por exemplo:
px=(int (*)[10]) calloc(10, sizeof(int));

A sentença
int *py[10];
corresponde a definir que py é um arranjo de ponteiros, py corresponde a um arranjo de 10 ponteiros para int; neste caso não é alocada 1(uma) variável e o que ocorre é a alocação de 10 elementos indexáveis cada um deles do tipo ponteiro para int.

Todas as afirmações acima só fazem sentido para definições de arranjos e ponteiros no corpo das funções! Qualquer tentativa de definir arranjos na lista de parâmetros de funções resulta na definição de ponteiros. Exemplo, em void f(){int ai[5];} ai é uma constante e define-se um arranjo de 5 int’s, mas em void f(int ai[5]){} ai é uma variável do tipo ponteiro e arranjos nunca, diretamente(*), aparecem como parâmetros. (*) mas podemos “embrulhar” arranjos em estruturas.

É possível escrever sentenças quase que ininteligíveis envolvendo arranjos e ponteiros, estas sentenças podem ficar mais legíveis se forem acrescentados “typedefs” de forma adequada.

A discussão acima pode ser generalizada para arranjos multidimensionais e ponteiros para arranjos multidimensionais. A definição do ponteiro tem que especificar as dimensões para que expressões do tipo *(*(p+2)+3) façam sentido.

O trecho abaixo exemplifica a “correspondência”  entre um ponteiro para arranjos de arranjos de int e um arranjo de arranjos de arranjos de int:

  int aaai[2][3][2]={{{10,20}, {30,40},{50,60}},{{70,80},{90,100},{110,120}}};
  int (*paai)[3][2];
  int pr;
  paai=aaai; //paai=&aaai[0];
  for(li=0; li<2; li++) 
    for(co=0; co<3; co++) 
      for(pr=0; pr<2; pr++)
        printf("%d ", aaai[li][co][pr]);
  printf("\n");
  for(li=0; li<2; li++)
    for(co=0; co<3; co++)
      for(pr=0; pr<2; pr++)
        printf("%d ", paai[li][co][pr]);

 

-------

O sistema de execução do ambiente da linguagem C inicia a execução dos programas a partir da função main(). Quando a função main() é invocada isto ocorre com dois argumentos. O primeiro, convencionalmente chamado argc (argument count: conta argumentos) é o número de argumentos da linha de comando. O segundo parâmetro, convencionalmente chamada argv (argument vector: vetor de argumentos [acredito que seria melhor arga (argument array: arranjo de argumentos)]) é um ponteiro para um arranjo de ponteiros de caracteres ou mais realisticamente um ponteiro para um arranjo de ponteiros de strings (cadeias de caracteres).

O programa abaixo exemplifica o uso destes argumentos:

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

int main(int argc, char *argv[]){
  int cnt;

  printf("Este programa foi invocado com %d argumentos:\n", argc);
  for(cnt=0; cnt<argc; cnt++){
    printf("argumento 1:%s\n", argv[cnt]); //imprime cada argumento
  }

  system("PAUSE");
  return 0;
}

Observe que em certos ambientes (em particular IDEs com interface gráfica, como o DEV-C++) é necessário especificar em uma janela de propriedades os argumentos. Cada argumento será armazenado com o zero/caractere nulo ao final e é por isto que é possível usar a letra de conversão ‘s’ (string). Outra opção é usar a interface de linha de comando para a execução. No caso do DEV-C++:
Execute->Parameters...

Abaixo temos duas versões para o cálculo dos digitos verificadores, onde um CPF é fornecido na linha de comando. Na primeira versão nada é verificado e acredita-se que a linha de comando vai ser fornecida corretamente

#include <stdio.h>
#include <stdlib.h>
//este programa utiliza o numero de
//cpf fornecido na linha de comando: prog 123456789
int main(int argc, char *argv[]){
  int d[9]; //d[0] unidade d[8] centena de milhoes
  int cnt;
  for(cnt=0; cnt<9; cnt++) d[cnt]=argv[1][8-cnt]-'0';
  int somaProd1, somaProd2, restoAux, dezena, unidade;
  somaProd1=0;
  for(cnt=0; cnt<9; cnt++) somaProd1+=d[cnt]*(cnt+2);
  restoAux=somaProd1%11;
  dezena=restoAux<2 ? 0 : 11-restoAux;
  somaProd2=dezena*2;
  for(cnt=0; cnt<9; cnt++) somaProd2+=d[cnt]*(cnt+3);
  restoAux=somaProd2%11;
  unidade=restoAux<2 ? 0 : 11-restoAux;
  printf("%s-%c%c\n", argv[1], dezena+'0', unidade+'0');
  return 0;

Já a versão abaixo faz uma série de verificações e escreve mensagens tentando avisar o tipo de problema encontrado.

#include <stdio.h>
#include <stdlib.h>
//este programa utiliza o numero de
//cpf fornecido na linha de comando
int main(int argc, char *argv[]){
  if(argc!=2){// existe 1 argumento?
    printf("CPF deve ser fornecido na linha de comando.\n");
    return 0;
  }
  if(strlen(argv[1])!=9){ //argumento com 9 caracteres?
    printf("CPF deve ser fornecido com 9 digitos.\n");
    return 0;
  }
  int digitosOk=1;
  int cnt;
  for(cnt=0; cnt<9 & digitosOk ; cnt++)
    digitosOk=digitosOk& argv[1][cnt]>='0'&argv[1][cnt]<='9';
  if(!digitosOk){ //9 caracteres são de 0 a 9?
    printf("CPF deve ser fornecido com 9 digitos de 0 a 9.\n");
    return 0;
  }
  int d[9]; //d[0] unidade d[8] centena de milhoes
  for(cnt=0; cnt<9; cnt++) d[cnt]=argv[1][8-cnt]-'0';
  int somaProd1, somaProd2, restoAux, dezena, unidade;
  somaProd1=0;
  for(cnt=0; cnt<9; cnt++) somaProd1+=d[cnt]*(cnt+2);
  restoAux=somaProd1%11;
  dezena=restoAux<2 ? 0 : 11-restoAux;
  somaProd2=dezena*2;
  for(cnt=0; cnt<9; cnt++) somaProd2+=d[cnt]*(cnt+3);
  restoAux=somaProd2%11;
  unidade=restoAux<2 ? 0 : 11-restoAux;
  printf("%s-%c%c\n", argv[1], dezena+'0', unidade+'0');
  return 0;
}
---

O programa abaixo calcula os dígitos verificadores de um CNPJ fornecido através da linha de comando.

#include <stdio.h>
#include <stdlib.h>
//este programa utiliza o numero de
//cnpj fornecido na linha de comando: prog 123456789123
int main(int argc, char *argv[]){
  if(argc!=2){// existe 1 argumento?
    printf("CNPJ deve ser fornecido na linha de comando.\n");
    return 0;
  }
  if(strlen(argv[1])!=12){ //argumento com 12 caracteres?
    printf("CNPJ deve ser fornecido com 12 digitos.\n");
    return 0;
  }
  int digitosOk=1;
  int cnt;
  for(cnt=0; cnt<12 & digitosOk ; cnt++)
    digitosOk=digitosOk& argv[1][cnt]>='0'&argv[1][cnt]<='9';
  if(!digitosOk){ //12 caracteres são de 0 a 9?
    printf("CNPJ deve ser fornecido com 12 digitos de 0 a 9"
     "sem barra, sem pontos.\n");
    return 0;
  }
  int d[12]; //d[0] unidade
  for(cnt=0; cnt<12; cnt++) d[cnt]=argv[1][11-cnt]-'0';
  int somaProd1, somaProd2, restoAux, dezena, unidade;
  somaProd1=0;
  for(cnt=0; cnt<8; cnt++) somaProd1+=d[cnt]*(cnt+2);
  for(cnt=8; cnt<12; cnt++) somaProd1+=d[cnt]*(cnt-6);
  restoAux=somaProd1%11;
  dezena=restoAux<2 ? 0 : 11-restoAux;
  somaProd2=dezena*2;
  for(cnt=0; cnt<7; cnt++) somaProd2+=d[cnt]*(cnt+3);
  for(cnt=7; cnt<12; cnt++) somaProd2+=d[cnt]*(cnt-5);
  restoAux=somaProd2%11;
  unidade=restoAux<2 ? 0 : 11-restoAux;
  printf("%s-%c%c\n", argv[1], dezena+'0', unidade+'0');
  return 0;
}

Arranjos de arranjos

Na definição de um arranjo podemos usar além dos tipo primitivos qualquer outro tipo “composto”. O arranjo é um destes tipos “compostos”. Observe a sentença abaixo:
int arranjoDeArranjo[2][3];

Trata-se de definir um arranjo de 2 elementos do tipo arranjo de 3 int’s. São definidas seis variáveis todas elas de tipo int.
Uma sentença do tipo:
  int aai[2][3];
de uma maneira “grosseira” corresponde a seis variáveis
  int aai00, aai01, aai02, aai10, aai11, aai12;
mas as seis variáveis são: aai[0][0], aai[0][1],aai[0][2], aai[1][0], aai[ 1][1], aai[1][2];

A iniciação ou inicialização de arranjos de arranjos deve ser feita aninhando os pares de abre e fecha chaves:

int aai[2][3]={{10,20,30},{40,50,60}};
Observe a existência de duas “linhas” e três “colunas”. Dizemos que a linguagem C armazena valores por linhas!
Ainda com relação a esta última sentença o identificador aai tem tipo arranjo[2] de arranjo[3] de int,. as expressões aai[0] e aai[1] têm o tipo arranjo[3] de int; A simplificação de que a expressão envolvendo arranjo equivale a endereço sem o uso do operador & existe para os componentes:
int *pi;
pi=aai[1]; // ou pi=&aai[1][0];
printf("%d %d %d\n", *pi,*(pi+1),*(pi+2));

int (*pai)[]; // pai=ponteiro para arranjo[] de int
pai=&aai[1];
printf("%d %d %d\n", (*pai)[0], (*pai)[1], (*pai)[2]);
-----

Exercícios:

---
Considere as seguintes declarações:

Escreva um programa que lista o conteúdo do arranjo ai (i)via ai (arranjo de int)  (ii) via p (ponteiro para int) e (iii) via pa (ponteiro para arranjo de int);

-----

 

Representação de relação binária

Uma relação definida sobre n elementos pode ser representada utilizando um arranjo de arranjos de ints. O arranjo de arranjos deve corresponder a uma matriz quadrada de tamanho n*n. Considere que r é um arranjo de arranjos representando tal matriz. O componente r[i][j] é “verdadeiro” (valor diferente de zero) quando o elemento correspondente a i está relacionado com o elemento correspondente a j. Se r[i][j] é “falso” (valor igual a zero) então i não se relaciona com j. A partir desta definição é fácil ver que podemos definir 16 relações sobre o conjunto {a,b}. são exemplos destas relações o conjunto vazio representado por{{false, false},{false, false}}, o conjunto{(a,b),(b,a)} representado por {{false,true},{true,false}} e o conjunto {(a,a), (a,b), (b,a), (b,b)} representado por {{true, true}, {true,true}}. Escreva um programa que para uma dada relação representada como descrito:

·         Testa se a relação é simétrica

·         Testa se a relação é assimétrica.

·         Testa se a relação é anti-simétrica.

·         Testa se a relação é transitiva.

·         Testa se a relação é reflexiva

·         Testa se a relação é de equivalência.

Os arranjos nos permitem expressar alguns algoritmos para ordenação dos valores.

Quadrados Mágicos

Um quadrado mágico de ordem Ncorresponde a uma matriz quadrada NxN onde os NxN valores são distintos e correspondem aos inteiros 1,2...NxN, além disso em cada linha, em cada coluna, em cada diagonal a soma dos elementos resulta em um mesmo valor denominado Constante Mágica=N(NxN+1)/2. Não existem quadrados mágicos de ordem 2! Um exemplo de quadrado mágico de ordem 3 é: {{2,7,6},{9,5,1},{4,3,8}} Para os quadrados de ordem 3, 4, 5,  ... a constante mágica é 15, 34, 65, 111, 175, 260, ...

2

7

6

9

5

1

4

3

8

 

Faça um programa que testa se um arranjo de arranjos de ints corresponde a um quadrado mágico. Se você não conseguir uma boa solução veja esta solução incompleta.

Quadrados Latinos

Um quadrado latino corresponde a uma matriz quadrada NxN onde os valores tanto nas linhas quanto nas colunas correspondem a uma permutação do valores 0,1,2,...N-1 (ou 1,2 , ...N) ou mais genericamente as linhas e colunas correspondem a permutações de N símbolos distintos. Existem apenas dois quadrados latino 2x2: {{0,1},{1,0}} e {{1,0},{0,1}} usando 0 e 1 ( ou {{1,2},{2,1}} e {{2,1}, {1,2}} usando 1 e 2).

Existem quantos quadrados latinos 3x3? Estes números formam uma seqüência e estão presentes em uma página de um sítio WWW que coleciona seqüências de inteiros(http://www.research.att.com/~njas/sequences/A002860)

01:1,
02:2,
03:12,
04:576,
05:161280,
06:812851200,
07:61479419904000,
08:108776032459082956800,
09:5524751496156892842531225600,
10:9982437658213039871725064756920320000,
11:776966836171770144107444346734230682311065600000

Ou seja existem 12 quadrados latinos 3x3. Faça um programa que testa se um arranjo de arranjos de ints codifica um quadrado latino (Considere representações utilizando int[][] e char[][]). Testar se um arranjo corresponde a um quadrado latino é um problema bem simples.

Um problema bastante complexo é gerar de maneira eficiente os quadrados latinos de ordem N. Existem várias técnicas para gerar de maneira sistemática “matrizes candidatas” a serem quadrados latinos. Uma técnica simples (e ineficiente) corresponde a esta função:
#define N <valor>
void gera(int m[][N], int ordem){
  int i,j;
  for(i=N-1; i>=0; i--)
    for(j=N-1; j>=0; j--){
      m[i][j]=ordem%N;
      ordem=ordem/N;
    }
}
Esta função gera todas as matrizes onde o elemento m[i][j] é um valor da gama de 0 a N-1, ou seja são N*N “dígitos” cada um podendo assumir N valores. A geração é controlada pelo parâmetro ordem. Para N=2 são 4 dígitos binários, devem ser geradas 16 matrizes, onde ordem 0 corresponde a {{0,0},{0,0}}, ordem 1 corresponde a {{0,0},{0,1}} e ordem 15 corresponde a {{1,1},{1,1}}. Para N=3 são 9 dígitos “trinários” devem ser geradas 19.683 matrizes, para N=4 são 16 dígitos cada um variando de 0 a 3, devem ser geradas 4.294.967.296 matrizes.

Uma técnica um pouco mais eficiente consiste em gerar as linhas (ou as colunas) a priori e gerar linha por linha ao invés de gerar elemento a elemento. Para a função abaixo, onde N=4, deveremos gerar apenas 331.776 matrizes ao invés de 4.294.967.296:

int perm[24][N]={{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},
                 {0,3,1,2},{0,3,2,1},{1,0,2,3},{1,0,3,2},
                 {1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
                 {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},
                 {2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},
                 {3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}};
void gera(int m[][N], int ordem){
  int i,j;
  int lin[4];
  lin[0]=ordem%24;
  lin[1]=ordem/24%24;
  lin[2]=ordem/(24*24)%24;
  lin[3]=ordem/(24*24*24)%24;
  for(i=N-1; i>=0; i--)
    for(j=N-1; j>=0; j--)
      m[N-1-i][j]=perm[lin[i]][j];
}

A indexação acima pode ser simplificada (p.ex. m[N-1-i][j] pode ser substituido por m[i][j]). A forma acima é apenas para tornar a apresentação mais inteligível em termos de “lexicografia”. A geração de matrizes no caso da função acima pode ser entendida como sendo a geração de números de N dígitos onde cada dígito pode ter N! valores. Técnicas mais sofisticadas são necessárias para tratar matrizes maiores.

Sudoku

Um sudoku “clássico” é um quadrado latino 9x9 com restrições adicionais: cada um dos nove quadrados 3x3 devem conter símbolos distintos, ou seja, um Sudoku é um quadrado latino 9x9 que contem 9 quadrados mágicos 3x3. Conforme visto acima temos:
5524751496156892842531225600 quadrados latinos; segundo Bertram Felgenhauer and Frazer Jarvis temos:
6670903752021072936960 grades de sudoku; As restrições adicionais reduziram da ordem de 10 elevado a 6!Uma redução da ordem de um milhão!

O programa abaixo verifica as restrições relacionadas ao arranjo 9x9 ser um quadrado latino:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE

int sudokuValido(int s[][9]){
  int i,j,k;
  int m,n;
  int digVisto[10];

  for(i=0; i<9; i++){
    for(k=1; k<10; k++) digVisto[k]=FALSE;
    for(j=0; j<9; j++){
      if(digVisto[s[i][j]]){
         printf("Repete o digito %d na linha %d\n", s[i][j],i);
         return FALSE;
      }
      digVisto[s[i][j]]=TRUE;
    }
    for(k=1; k<10; k++) digVisto[k]=FALSE;
    for(j=0; j<9; j++){
      if(digVisto[s[j][i]]){
      printf("Repete o digito %d na coluna %d\n", s[j][i],i);
      return FALSE;
      }
      digVisto[s[j][i]]=TRUE;
    }
  }
  return TRUE;
}

int main(int argc, char *argv[])
{
    int s[9][9]={{5,3,4,6,7,8,9,1,2},
                 {6,7,2,1,9,5,3,4,8},
                 {1,9,8,3,4,2,5,6,7},
                 {8,5,9,7,6,1,4,2,3},
                 {4,2,6,8,5,3,7,9,1},
                 {7,1,3,9,2,4,8,5,6},
                 {9,6,1,5,3,7,2,8,4},
                 {2,8,7,4,1,9,6,3,5},
                 {3,4,5,2,8,6,1,7,9}};
  if(sudokuValido(s))
    printf("sudoku ok!\n");
  system("PAUSE");
  return 0;
}

Complete o programa acima para verificar se os nove quadrados 3x3 contêm digitos distintos, completando assim a verificação da validade do sudoku. Se depois de insistir (não clique agora!) não conseguir uma boa solução veja esta sugestão.

O programa abaixo mostra uma outra maneira de verificar a unicidade dos elementos das linhas e colunas:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE
int sudokuValido(int s[][9]){
  int i,j,k,v;
  int m,n;
  for(i=0; i<9; i++){
    for(j=0; j<9; j++){
      v=s[i][j];
      for(k=j+1; k<9; k++)
        if(v==s[i][k]){
           printf("Repete o digito %d na linha %d\n", s[i][j],i);
           return FALSE;
        }
    }
    for(j=0; j<9; j++){
      v=s[j][i];
      for(k=j+1; k<9; k++)
        if(v==s[k][i]){
        printf("Repete o digito %d na coluna %d\n", s[j][i],i);
        return FALSE;
        }
    }
  }
  return TRUE;
}

int main(int argc, char *argv[])
{
    int s[9][9]={{5,3,4,6,7,8,9,1,2},
                 {6,7,2,1,9,5,3,4,8},
                 {1,9,8,3,4,2,5,6,7},
                 {8,5,9,7,6,1,4,2,3},
                 {4,2,6,8,5,3,7,9,1},
                 {7,1,3,9,2,4,8,5,6},
                 {9,6,1,5,3,7,2,8,4},
                 {2,8,7,4,1,9,6,3,5},
                 {3,4,5,2,8,6,1,7,9}};
  if(sudokuValido(s))
    printf("sudoku ok!\n");
  system("PAUSE");
  return 0;
}

Quantas matrizes 3x3 envolvendo os valores de 1 a 9 podem ser construídas? A geração de sudokus a partir da geração de matrizes de quadrados latinos utilizando a geração elemento a elemento é inviável. Teriamos que gerar  da ordem de 10 elevado a 77 matrizes. A geração de sudokus a partir de quadrados latinos com geração linha a linha, também é inviável, envolve a geração de 9 elevado a 9!= 362880 matrizes, ou seja “apenas” da ordem de 10 elevado a 50.

Kenken

Um Kenken é um quadrado latino NxN com restrições adicionais: são demarcadas regiões ou gaiolas ou jaulas (cages) (conexas!) e são associadas a estas regiões um valor e uma operação aritmética (a exceção é quando a região consiste de somente uma célula e neste caso existe apenas o valor). Um kenken válido além de obedecer às restrições dos quadrados latinos obedece à restrição de que uma região demarcada deve ter células com valores tais que usando a operação aritmética associada obtem-se o valor associado à região. Invente algumas maneiras de codificar um Kenken.
Observe o exemplo a seguir:

Poderiamos codifica-lo, por exemplo, como sendo um (i)arranjo 4x4 de ints para os valores. As regiões poderiam ser representadas (REP1) na forma de um arranjo contendo identificadores de regiões: int cage[4][4]={{1,1,2,2}, {3,4,4,5},{3,6,7,8},{6,6,7,8}} ou (REP2) na forma de uma lista contendo identificadores de células: 1: {(0,0), (0,1)},  2: {(0,2), (0,3)},  3:{(1,0),(2,0)},  4:{(1,1),(1,2)},  5:{(1,3)},  6:{(2,1),(3,0),(3,1)}, 7:{(2,2),(3,2)}, 8:{(2,3),(3,3)}

Faça um programa que transforma um kenken na forma REP1 para a forma REP2

Faça um programa que transforma um kenken na forma REP2 para a forma REP1

Faça um programa que dada uma configuração de kenken ele determina se é uma configuração válida.

Imagine outras representações para o Kenken, quais as vantagens? quais as desvantagens?
 
 
  Vários programas podem ser feitos explorando problemas simples mas motivadores e que trazem grande aprendizado:

1.      Faça programas que aceitem diferentes codificações para configurações do clássico jogo-da-velha e imprimem uma dada configuração. Algumas sugestões de codificação:
char jv[3][3]={“XOO”, “OXX”, “OOX”};
char jv[3][3]={{‘X’,’O’, ‘O’},{‘O’, ‘X’, ‘X.’}, {‘O’, ‘O’, ‘X’}};
int jv[3][3]={{2,1,1},{1,2,2}, {1,1,2}};
int jv[3][3]={{-1,1,1},{1,-1,-1},{1,1,-1}};

2.      Faça programas que verifiquem se uma dada configuração de jogo da velha, codificada de alguma forma, é valida, (defina esta “validade estática”). Considere a seguinte codificação:
int jv[3][3]={{-1,0,0},{0,1,0},{0,0,0}};
Nesta codificação uma posição não preenchida do jogo é codificada com o valor int 0, uma opção do jogador

3.      Uma outra opção de codificação é codificar a ordem das jogadas de cada jogador. Na codificação abaixo o primeiro jogador tem sua jogadas codificadas com valores negativos, as posições não preenchidas estão codificadas com o valor 0 e as jogadas do segundo jogador estão codificadas com valores positivos:
int jv1[3][3]={{0,0,0},{0,0,0},{0,0,0}};
int jv2[3][3]={{0,0,0},{0,-1,0},{0,0,0}};
int jv3[3][3]={{1,0,0},{0,-1,0},{0,0,0}};
int jv4[3][3]={{1,0,0},{-2,-1,0},{0,0,0}};
int jv5[3][3]={{1,0,0},{-2,-1,2},{0,0,0}};

4.      Faça um programa que verifica se uma configuração de jogo-da-velha pode ser a jogada seguinte de uma outra configuração.

5.      Faça um programa que gera e imprime quais são as configurações que podem corresponder às jogadas seguintes de uma dada configuração.

6.      Vários outros jogos e quebra-cabeças podem ser usados na confecção de programas simples. No jogo “Nurikabe”(haverá discussões à frente na disciplina) você recebe usualmente um tabuleiro quadrado de NxN posições (mas existem nurikabes de tamanho NxM). Em algumas posições existem números maiores ou iguais a 1. Estes números especificam o número de posições do tabuleiro que não devem ser cobertas com blocos de cobertura (BC) seguindo algumas regras: (i)os BCs não podem formar áreas maiores que 2x2 e de um BC você deve poder ir até outro BC qualquer através de conexões laterais (não vale diagonais!), as posições de áreas não cobertas devem ter contiguidade lateral (não vale conexão pelas diagonais!).
Considere a seguinte codificação de um jogo de Nurikabe em um tabuleiro 5x5:
int nurikabe[5][5]={{3,0,0,0,2},{0,0,0,0,0},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
Nesta codificação os números maiores que zero representam o número de posições que não devem ser cobertas e os zeros representam as posições que podem ou não cobertas.
uma solução para esta instância é:
int solucao[5][5]={{3,0,0,-1,2}, {-1,-1,-1,-1,0}, {2,-1,0,4,-1},{0,-1,0,0,-1}, {-1,-1,-1,-1,-1}};
Nesta codificação as posições que foram cobertas são indicadas através do valor -1
Faça um programa que testa se uma dada configuração é solução para uma instância de nurikabe.

7.      Faça um programa que gera “algumas” configurações iniciais para uma dada solução de Nurikabe. Por exemplo, para a solução apresentada anteriormente:
int solucao[5][5]={{3,0,0,-1,2}, {-1,-1,-1,-1,0}, {2,-1,0,4,-1},{0,-1,0,0,-1}, {-1,-1,-1,-1,-1}};
podemos ter as seguintes configurações iniciais (além da apresentada):
int nurikabe[5][5]={{0,3,0,0,2},{0,0,0,0,0},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
int nurikabe[5][5]={{0,0,3,0,2},{0,0,0,0,0},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
int nurikabe[5][5]={{3,0,0,0,0},{0,0,0,0,2},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
int nurikabe[5][5]={{0,0,3,0,0},{0,0,0,0,2},{0,0,0,0,0},{2,0,4,0,0},{0,0,0,0,0};

8.      O programa abaixo calcula e armazena em um arranjo a sequência de números primos a partir de 2 e 3. Explique porque é usada a expressão ehPrimo&&p/primos[ii]>=primos[ii] para limitar o laço interno.
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE

int main(int argc, char *argv[]){
  int N=500, ind=2, primos[N], p,ii;
  int ehPrimo;
  primos[0]=2; primos[1]=3;
  for(p=5; p<=N; p=p+2){
    ehPrimo=TRUE;
    for(ii=1; ehPrimo&&p/primos[ii]>=primos[ii]; ii++)
      ehPrimo=p%primos[ii]!=0;
    if(ehPrimo) primos[ind++]=p;
  }
  for(ii=0; ii<ind; ii++) printf("%i ", primos[ii]);
  printf("\n");
  system("PAUSE");
  return 0;
}

9.      Faça um programa que dado um arranjo representando uma configuração de minas no estilo do jogo “varrendo as minas” (Mine Sweeper) ele gera os números de 0 a 8 que representam o número de minas que circundam uma dada posição. Assim, dada uma área retangular onde as minas são representadas pelo número 9:
****9**
**9***9
9999***
99*9**9
*999**9
(o asterisco * representa posições que não são minas!) deverá ser gerada a matriz:
0112911
2494129
9999222
9989329
3999229

Considere um arranjo 2x2x2 contendo 8 elementos com os valores 1,2,3,4,5,6,7,8; Dê a definição e inicialização na linguagem C deste arranjo tal que as linhas (saguão) sejam (1,2) (3,4), (5,6) e (7,8), as colunas (torres) sejam (1,3), (2,4), (5,7) e (6,8) e as profundidades (corredores) sejam (1,5), (2,6), (3,7) e (4,8).

 

Mastermind ( Senha )

O jogo “Mastermind” tem grande número de variantes. A variante mais “tradicional” corresponde a 6 objetos distintos devem ser escolhidos 4 deles e a resposta a uma tentativa de advinhar a escolha consiste em dois componentes: (i) número de objetos corretos na posição correta e (ii) número de objetos corretos na posição incorreta. Considere que os seis objetos possíveis são os valores 0,1,2,3,4 e 5; considere que a escolha foi 0112 (dentre as 6x6x6x6=1296 possíveis). A resposta pode ser codificada em um número de dois dígitos onde a unidade corresponde aos objetos corretos na posição incorreta e a dezena corresponde aos objetos corretos na posição correta.

Faça um programa que examina o espaço de soluções do jogo mastermind. Qual a melhor estratégia para a primeira jogada? Existem basicamente somente 5 tipos de escolhas iniciais 0000, 0001, 0011, 0012, 0123!

Verifique se a distribuição dos valores de respostas para a primeira tentativa na tabela abaixo estão corretos:

Resp

 

0000

0001

0011

0012

0123

0

00

625

256

256

81

16

1

01

0

308

256

276

152

2

10

500

317

256

182

108

3

02

0

61

96

222

312

4

11

0

156

208

230

252

5

20

150

123

114

105

96

6

03

0

0

16

44

136

7

12

0

27

36

84

132

8

21

0

24

32

40

48

9

30

20

20

20

20

20

10

04

0

0

1

2

9

11

13

0

0

0

4

8

12

22

0

3

4

5

6

13

40

1

1

1

1

1

Observe que a escolha com “menor máximo”é 0011 ! (retirado de http://www.tnelson.demon.co.uk/mastermind/).

Para uma “ajuda” na tarefa de verificar o quadro este programa gera as 3 primeiras colunas!