C Problema Linguagem C - Vetores e Matrizes

[Danizinha CM]

@isrnick @arfneto Rapazes, eu agradeço imensamente a ajuda de vocês, e também a paciência. Eu li, reli, tentei implementar as suas dicas mas infelizmente não consigo dar um passo à frente nesse código, na impressão da matriz com os valores aleatórios, nunca sai do jeito que tem que sair.  Obrigada de coração! Abraços!

[arfneto]

Em 14/06/2019 às 14:17, Daniela Calfat Maldaun disse:

@isrnick @arfneto Rapazes, eu agradeço imensamente a ajuda de vocês, e também a paciência. Eu li, reli, tentei implementar as suas dicas mas infelizmente não consigo dar um passo à frente nesse código, na impressão da matriz com os valores aleatórios, nunca sai do jeito que tem que sair.  Obrigada de coração! Abraços!

 

Provavelmente fez bem você  em não insistir no trabalho tendo apenas 2 dias pra terminar e com toda a dificuldade. De todo modo, vou postar o que seria meu palpite. Pode ser útil pra você entender o que acontecia, se voltar a isso, ou pode ajudar alguém interessado nessas coisas ou pensando em implementar uma versão de campo minado
Essas funções são só uma prova de conceito, para ajudar a implementar o jogo. Pequenas partes que pode testar em separado.
Imagine seu tabuleiro declarado assim:
 

Você controla o tamanho em uso através dos valores que leu do usuário no início do programa, m linhas por n colunas com z minas, mas declara o tabuleiro com o tamanho máximo, que não é assim tão grande afinal.

Os valores estranhos que viu em seu programa podem ser devidos a você não ter inicializado o tabuleiro com nada conhecido, e o seu compilador não inicializar talvez com zero automaticamente.

Para imprimir, pode pensar em uma função como essa abaixo, que só mostra as células em  uma --- talvez muito longa --- linha por vez, mostra()

 

Note que se quer por exemplo colocar um valor conhecido nas células para ajudar a testar e formatar os campos, pode usar algo como essa mínima função numera()

 

 

Na hora de colocar as minas no tabuleiro, pode usar algo como essa rotina poe_as_minas() aqui, que usa a ideia que expliquei em detalhe num post anterior, como deve ter visto.

@isrnick aqui disse que essa lógica que eu expliquei no outro post tem até um nome! Nunca pensei nisso, porque é uma coisa tão ingênua... Mas sei como o mundo acadêmico é cheio disso e os caras querem o crédito de tudo. Eu não teria coragem de reivindicar a ideia de algo tão besta, ou mesmo por meu nome: você tem um certo número de minas pra colocar e um certo número de posições livres no tabuleiro. Então sorteia uma posição. Vai no tabuleiro e conta de um em um a partir do início, mas tomando o óbvio cuidado de pular as células vazias. Eu uso isso desde moleque quando (tentava) simular jogos de cartas.

 

Só isso. Claro, o método de Knuth/Fisher/Yates não tem esse lance de pular posições ocupadas. É só a maneira de sortear as coisas. Podia chamar isso aqui de Knuth/Fisher/Yates/arfneto  Ok essa foi pobre. De volta ao tópico

Essa é  uma possível implementação. Tem apenas um loop para colocar as minas e uns ajustes pra pular as células que já tenham uma mina. Não é nada autoritativo, devem haver por certo melhores maneiras de fazer isso. E piores. Mas essa funciona com um número mínimo de operações. A função auxiliar que avança os índices está a seguir. Bem simples, deixei fora para facilitar o entendimento do loop.

 

 

@isrnick Se conhecia esse método ou teve essa ideia, não entendo como sugere implementar com um vetor auxiliar e um novo nível de índices. Devo ter perdido algo

Imagino que tenha explicado isso no meio desse tópico antigo de 2018, e não aqui onde o autor do tópico poderia acessar de imediato. De todo modo ao embaralhar todo o vetor em um outro vai "sortear" 8099 casas para 8100 valores, no caso de 90x90. Sabendo, como você diz, que não é preciso. Para colocar 200 minas, 8099 sorteios. Para 4 minas, 8099 sorteios...
Mesmo sabendo que bastariam n sorteios para n minas, como você disse. E quanto à facilidade de entender a lógica, tenho também dúvida: ao invés de ir lá sortear 4 vezes para 4 minas, vai usar 8099 veze o sorteio  para criar uma outra estrutura, como um outro tabuleiro ou vetor como disse, e aí nesse outro tabuleiro pegar as posições das 4 minas, como sugeriu. E o aluno, ou o autor do tópico aqui, vai ter que entender um segundo nível de índices, porque a posição da mina não vai ser a posição tabuleiro[j] mas sim a posição tabuleiro[ coisa ] [ coisa[j] ] já que vai ter que declarar essa coisa para poder reordenar.

E nem é necessário: você pode muito bem fazer essa reordenação no próprio tabuleiro, usando o mesmo método cujo nome citou, e a lógica que eu expliquei  uns posts atrás. Isso  porque a cada embaralhamento o número de células livres diminui e  então pode ir extraindo as novas posições e colocando no início, já que elas não serão revisitadas pelo algoritmo...  No caso desse jogo não faria sentido, porque eu não vejo razão para reordenar todas as células m*n sabendo que só precisa de z. E note que nesse caso z<15 por definição. Pense nisso. Dependendo de sua experiência com essas coisas, creio que não terá dificuldade em implementar o que alguém chamaria de inline shuffling nesse tabuleiro. 

Acho que pode ser útil para muitos essa implementação. Se quiser pode abrir um tópico e deixamos aqui para o pessoal. Sem nossos nomes  

@Daniela Calfat Maldaun
Eis como seria um programa principal pra rodar isso, depois de ler os valores na tela:

	printf("\nBem vindo ao Caça-Minas!\n");
	printf("\n=======================================\n");
	printf("Eis a tabela como veio ao mundo:\n");
	mostra();
	numera();
	printf("\n=======================================\n");
	printf("Agora numerando as celulas:\n");
	mostra();
	// agora vamos testar isso com um exemplo
	srand(seed);
	printf("\nIniciou o gerador com a semente %d, como pedido\n", seed);
	printf("Agora vai colocar as %d minas no tabuleiro de %d x %d\n", z, m, n);
	poe_as_minas();
	printf("\n=======================================\n");
	printf("Agora com -1 onde esao as minas:\n");
	mostra();

E um exemplo da tela:

 

Boa sorte!

Continue programando!

[isrnick]

15 horas atrás, arfneto disse:

@isrnick aqui disse que essa lógica que eu expliquei no outro post tem até um nome! Nunca pensei nisso, porque é uma coisa tão ingênua... Mas sei como o mundo acadêmico é cheio disso e os caras querem o crédito de tudo. Eu não teria coragem de reivindicar a ideia de algo tão besta, ou mesmo por meu nome: você tem um certo número de minas pra colocar e um certo número de posições livres no tabuleiro. Então sorteia uma posição. Vai no tabuleiro e conta de um em um a partir do início, mas tomando o óbvio cuidado de pular as células vazias. Eu uso isso desde moleque quando (tentava) simular jogos de cartas.

 

Sim, esse é o método que eu fazia também, ir diminuindo o número de possibilidades após cada sorteio, e contar dês do início pulando as posições já sorteadas. É o jeito mais fácil de pensar em fazer isso logo como você cheguei ao mesmo método.

 

O único problema desse método é a complexidade assintótica do algoritmo, tem que percorrer a matriz toda vez que um número é sorteado, então no pior caso uma matrix com N posições, serão feitos N-1 sorteios, e percorrerá a matriz N vezes, logo N-1 sorteios vezes N/2 posições percorridas da matriz, a complexidade é O(N²).

 

 

15 horas atrás, arfneto disse:

@isrnick Se conhecia esse método ou teve essa ideia, não entendo como sugere implementar com um vetor auxiliar e um novo nível de índices. Devo ter perdido algo

 

A vantagem é que usando o algoritmo Fisher-Yates a complexidade assintótica no pior caso é O(N).

 

Sim, tem razão, usando o vetor auxiliar e sorteando z posições como falei aumenta o uso de memória.

 

Mas tem ainda outro método pra fazer ainda mais simples, sem o vetor auxiliar, basta por exemplo preencher as z primeiras casas da matriz m x n com minas (o restante não tem minas), e embaralhar os valores contidos na própria matriz.

 

Veja:

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

int main()
{
    srand(time(NULL));
    
    //Matriz 5 x 6
    int matriz[5][6] = {}, i, j, aux, n;
    //z é o número de casas com minas:
    int z = 10;
    
    //Inicialmente marca as z primeiras casas com minas
    for(i = 0; i < z; i++){
        matriz[i/6][i%6] = -1;
    }
    
    //imprime matriz
    printf("Matriz inicial\n");
    for (i = 0; i < 5; i++){
        for (j = 0; j < 6; j++){
            printf("%2d ", matriz[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    
    //Embaralha com algoritmo Fisher-Yates
    n = 5*6;
    for(i = 0; i < n-1; i++){
        //Sorteia uma das posições ainda não selecionadas restantes
        j = i + rand() % (n-i);

        //Faz a troca de valores da posição atual i com a sorteada j
        aux = matriz[i/6][i%6];
        matriz[i/6][i%6] = matriz[j/6][j%6];
        matriz[j/6][j%6] = aux;
    }
    
    //imprime matriz após embaralhar
    printf("Matriz embaralhada\n");
    for (i = 0; i < 5; i++){
        for (j = 0; j < 6; j++){
            printf("%2d ", matriz[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    
    return 0;
}

 

[isrnick]

 

 

@arfneto Não entendi muito bem o que você quis dizer sobre o número de sorteios e tal.

 

Mas para ficar claro vou postar aqui também o código como ficaria usando o vetor auxiliar e fazendo apenas z sorteios, como sugeri originalmente:

 

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

int main()
{
    srand(time(NULL));
    
    //Matriz 5 x 6
    int matriz[5][6] = {}, pos[5*6], i, j, aux, n;
    //z é o número de casas com minas:
    int z = 10;
    
    //Inicia cada posição em seu devido lugar
    n = 5*6;
    for(i = 0; i < n; i++){
        pos[i] = i;
    }
    
    //Embaralha com algoritmo Fisher-Yates
    for(i = 0; i < z; i++){ //Apenas z sorteios são realizados
        //Sorteia uma das posições ainda não selecionadas restantes
        j = i + rand() % (n-i);
        
        //Põe mina na posição sorteada
        matriz[ pos[j]/6 ][ pos[j]%6 ] = -1;
        
        //Faz a troca da posição atual i com a sorteada j
        //aux = pos[j]; //Não é necessário
        pos[j] = pos[i];
        //pos[i] = aux; //Não é necessário
        //As linhas comentadas acima estão aí só para mostrar a troca
        //que seria feita no algoritmo original, mas não é necessário
        //nesse caso, não usaremos a posição sorteada novamente, logo
        //não precisamos guardá-la.
    }
    
    //imprime matriz com as minas nas posições sorteadas
    printf("Matriz\n");
    for (i = 0; i < 5; i++){
        for (j = 0; j < 6; j++){
            printf("%2d ", matriz[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    
    return 0;
}

 

Como meu código anterior as vantagens de diminuição de complexidade e simplificação da lógica se mantém, e a "desvantagem" é que usa mais memória por causa do vetor auxiliar de posições.