Vocês poderiam me ajudar a analisar o seguinte código (sobre grafos)?

Juliano Balcante Pereira · 2 de agosto de 2015

Estou estudando grafos para a prova da OBI e decidi estudar os códigos e a lógica através de códigos já pronto;

O problema a ser resolvido está no seguinte endereço: http://olimpiada.ic.unicamp.br/pratique/programacao/nivel2/2009f1p2_pontes

O código é esse (solução proposta pela própria OBI):

/* Solucao para o problema "Caminho das Pontes" da OBI 2009   por: Igor Ribeiro de Assis */#include <stdio.h>#include <string.h> 		/* memset() */#define MAXN 1010/* matriz de adjacencias */int A[MAXN][MAXN], visitado[MAXN], dis[MAXN];int n, m;int dijkstra() {  int i;  memset(dis, 0x3f, sizeof(dis)); /* distancia inicial infinita */  memset(visitado, 0, sizeof(visitado));  dis[0] = 0;  for (; {    int no = -1;    for (i = 0; i < n; i++)      if (!visitado[i] && (no == -1 || dis[i] < dis[no]))	no = i;    if (no == -1) break;    visitado[no] = 1;    for (i = 0; i < n; i++)      if (dis[no] + A[no][i] < dis[i])	dis[i] = dis[no] + A[no][i];  }      return dis[n-1];}int main() {  int i;  int s, t, b;  scanf("%d%d", &n, &m);  n += 2; /* imagina os as bordas como pilares */  memset(A, 0x3f, sizeof(A));	/* numero de buracos infinito */  for (i = 0; i < m; i++) {    scanf("%d%d%d", &s, &t, &;    A[s][t] = A[t][s] = b;  }    printf("%d\n", dijkstra());  return 0;}

O que entendi desse código foi:

O grafo está sendo representado por matriz de adjacência;
Como o grafo é ponderado, para identificar os arcos está sendo utilizado o próprio peso da aresta;
Foi criado um vetor para a distância mínima;
Foi criado um vetor para marcar as visitadas ( não sei como);
A saída da função dijkstra() é a distância mínima percorrida, no caso a quantidade mínima de buracos;
A função memset() preenche um array com determinado valor;

Mas não entendi poruqe preenche o vetor dis[] com 0x3f. Tinha pesquisado e descobri que é 63 em número hexadecimal, mas por que 63 e por que em número hexadecimal?
O que significa os ';;' em "for (; {"?

Vocês poderiam me descrver como funciona a lógica dentro do for(;{}? Quando pesquisei sobre grafos não entendi como funciona aqueles visitados e não visitados...

vangodp · 2 de agosto de 2015

for(;

Tem o mesmo efeito que while(1).

Sobre o 0x3f não tem uma explicação fácil ou simples, a mais lógica é que ele colocou 0x3f ou 63 por que "teve vontade". O problema é que memset se usa para dar valores a vetores de chars(c_strings) já que precisamos informar um x numero de casinhas (não vale valores negativos "size_t" ) a serem formatadas como se explica nessa pagina http://www.cplusplus.com/reference/cstring/memset/, nesse caso cada casinha ia ganhar o valor de carácter '?'(conforme a tabela abaixo) pois memset formata chars não inteiros, na memoria cada char ocupa um byte e cada inteiro ocupa 4bytes(pode variar de um computador a outro). O valor hexdecimal 0x3f si retirar o 0x deixando 3f indica nessa tabela o carácter '?'.

Vamos tentar encontrar a lógica disso. Pesamos que temos um array de inteiros assim:

int arrray[100];

E que queremos formatar ele com 0x3f como no seu caso.

memset(array, 0x3f, sizeof(array));

Bem... recorde o anterior, porque agora vou tentar explicar alguns conceitos.

Si vou no meu computador e faço printf ("char=%d\nint=%d"sizeof(char),sizeof(int)); me imprime isso:

char=1

int =4

O anterior que imprimiu quer dizer o tamanho que ocupa em bytes(conjunto de 8bits) cada variável na nossa memoria. Então vamos pensar assim... Um char ocupa [0] e um inteiro ocupa [0][0][0][0] ok. o problema esta que si eu faço size of de array com printf ("%d",sizeof(array) me vai retornar um valor 4 vezes maior si o array for de inteiros que no caso de ser array de chars.

Prove isso:

char arrray[100];

printf ("%d",sizeof(array);

E logo depois em outro programa prove isso:

int arrray[100];

printf ("%d",sizeof(array);

Ambos dentro de um simples main claro.

O primeiro me vai imprimir 100, e o segundo vai imprimir 400! Por que isso? Porque como falei um inteiro ocupa [0][0][0][0](4Bytes) frente a char que ocupa [0] (1Byte), sizeof me devolve o tamanho em Bytes, e isso é o que memset quer saber, o tamanho em Bytes que tem o array, porque ele vai meter em cada byte o valor 0x3f ou o que é o mesmo 63. Isso não tem lógica? Ou sim?. XD

Agora já sabemos que memset independente do tipo do array, não importa si é int ou char, ele vai fazer isso: memset pega 0x3f e no caso de um char ele faz [0x3f], e no caso do array for de inteiros ele faz [0x3f][0x3f][0x3f][0x3f], ele recheia sizeof(array) numeros em Bytes com o valor 0x3f, si são 100 bytes, 100 bytes que ele vai encher com 0x3f, si são 400 o que devolve sizeof, pois 400 Bytes serão recheados com 0x3f.

Ainda não entendemos a lógica verdade? Por que 0x3f??? =(

Más provamos agora imprimir seu array mesmo ele sendo de inteiros como si ele fosse de chars dessa forma:

#include <stdio.h>#include <string.h>#define TAM 100int main (){    int i;    int array[TAM];    memset ( array, 63, sizeof(array) );        for(i=0; i<TAM; i++){        printf("array[i] contem: %c\n", array[i] );            }        getchar();    return 0;}

agora provamos como inteiro:

#include <stdio.h>#include <string.h>#define TAM 100int main (){    int i;    int array[TAM];    memset ( array, 63, sizeof(array) );        for(i=0; i<TAM; i++){        printf("array[i] contem: %d\n", array[i] );            }        getchar();    return 0;}

No caso de imprimir ele como char tem mais lógica não? Por que como inteiros sai um numero estranho 1061109567, isso no meu computador, más no seu pode ser até outro numero. Esse numero é o resultado de ter 0x3f en cada um do seus 4 Bytes de cada inteiro, isso é o representa esse numero. porém o numero não é o importante, o importante é o que representa esse numero, e acho mais lógico que ele represente '?' do que 1061109567. O que você não acha?

Más realmente não estou muito seguro do que estou contando aqui, por que só quem programou isso entende realmente o por que ele fez isso. Eu vou seguir investigando por minha conta e si tenho novidades já aviso aqui mesmo.

Juliano Balcante Pereira · 3 de agosto de 2015

Tem o mesmo efeito que while(1).

Sobre o 0x3f não tem uma explicação fácil ou simples, a mais lógica é que ele colocou 0x3f ou 63 por que "teve vontade". O problema é que memset se usa para dar valores a vetores de chars(c_strings) já que precisamos informar um x numero de casinhas (não vale valores negativos "size_t" ) a serem formatadas como se explica nessa pagina http://www.cplusplus.com/reference/cstring/memset/, nesse caso cada casinha ia ganhar o valor de carácter '?'(conforme a tabela abaixo) pois memset formata chars não inteiros, na memoria cada char ocupa um byte e cada inteiro ocupa 4bytes(pode variar de um computador a outro). O valor hexdecimal 0x3f si retirar o 0x deixando 3f indica nessa tabela o carácter '?'.

Vamos tentar encontrar a lógica disso. Pesamos que temos um array de inteiros assim:

int arrray[100];

E que queremos formatar ele com 0x3f como no seu caso.

memset(array, 0x3f, sizeof(array));

Bem... recorde o anterior, porque agora vou tentar explicar alguns conceitos.

Si vou no meu computador e faço printf ("char=%d\nint=%d"sizeof(char),sizeof(int)); me imprime isso:

char=1

int =4

O anterior que imprimiu quer dizer o tamanho que ocupa em bytes(conjunto de 8bits) cada variável na nossa memoria. Então vamos pensar assim... Um char ocupa [0] e um inteiro ocupa [0][0][0][0] ok. o problema esta que si eu faço size of de array com printf ("%d",sizeof(array) me vai retornar um valor 4 vezes maior si o array for de inteiros que no caso de ser array de chars.

Prove isso:

char arrray[100];

printf ("%d",sizeof(array);

E logo depois em outro programa prove isso:

int arrray[100];

printf ("%d",sizeof(array);

Ambos dentro de um simples main claro.

O primeiro me vai imprimir 100, e o segundo vai imprimir 400! Por que isso? Porque como falei um inteiro ocupa [0][0][0][0](4Bytes) frente a char que ocupa [0] (1Byte), sizeof me devolve o tamanho em Bytes, e isso é o que memset quer saber, o tamanho em Bytes que tem o array, porque ele vai meter em cada byte o valor 0x3f ou o que é o mesmo 63. Isso não tem lógica? Ou sim?. XD

Agora já sabemos que memset independente do tipo do array, não importa si é int ou char, ele vai fazer isso: memset pega 0x3f e no caso de um char ele faz [0x3f], e no caso do array for de inteiros ele faz [0x3f][0x3f][0x3f][0x3f], ele recheia sizeof(array) numeros em Bytes com o valor 0x3f, si são 100 bytes, 100 bytes que ele vai encher com 0x3f, si são 400 o que devolve sizeof, pois 400 Bytes serão recheados com 0x3f.

Ainda não entendemos a lógica verdade? Por que 0x3f??? =(

Más provamos agora imprimir seu array mesmo ele sendo de inteiros como si ele fosse de chars dessa forma:
#include <stdio.h>#include <string.h>#define TAM 100int main (){    int i;    int array[TAM];    memset ( array, 63, sizeof(array) );        for(i=0; i<TAM; i++){        printf("array[i] contem: %c\n", array[i] );            }        getchar();    return 0;}
agora provamos como inteiro:
#include <stdio.h>#include <string.h>#define TAM 100int main (){    int i;    int array[TAM];    memset ( array, 63, sizeof(array) );        for(i=0; i<TAM; i++){        printf("array[i] contem: %d\n", array[i] );            }        getchar();    return 0;}
No caso de imprimir ele como char tem mais lógica não? Por que como inteiros sai um numero estranho 1061109567, isso no meu computador, más no seu pode ser até outro numero. Esse numero é o resultado de ter 0x3f en cada um do seus 4 Bytes de cada inteiro, isso é o representa esse numero. porém o numero não é o importante, o importante é o que representa esse numero, e acho mais lógico que ele represente '?' do que 1061109567. O que você não acha?

Más realmente não estou muito seguro do que estou contando aqui, por que só quem programou isso entende realmente o por que ele fez isso. Eu vou seguir investigando por minha conta e si tenho novidades já aviso aqui mesmo.

Entendi, mas o que while(1) ou como está lá, while(; faz? Fica no loop enquanto o quê?

E acho que escolheram 0x3f ou ? apenas para preencher o array, funcionando apenas como um marcador inicial...

vangodp · 3 de agosto de 2015

Entendi, mas o que while(1) ou como está lá, while(; faz? Fica no loop enquanto o quê?

while(1) e for(; são bucles infinitos. Normalmente se usa quando o criador disponibiliza algum outro método para deter o bucle. Nesse caso o que se encarga disso é essa linha if (no == -1) break, o break se encarga de "quebrar" o loop. Tecnicamente a reposta a sua pergunta é. Fica no loop até que no seja igual que -1! Quando isso suceder o break; vai fazer o programa sair desse loop e parar justo depois da chave que fecha o while.

while(1) e for(; são loops infinitos. Leia isso: http://linguagemc.com.br/loop-infinito-em-c/

E acho que escolheram 0x3f ou ? apenas para preencher o array, funcionando apenas como um marcador inicial...

Exatamente! É somente um valor inicial para representar algo. Pode ser para representar que essa casinha da ponte não foi visitada ainda, ou que o personagem ainda não sabe se tem tabua ou é um buraco conforme vi assim por em cima o enunciado(É só uma suposição. XD).

Sorte.