C Problema Linguagem C - Vetores e Matrizes

Danizinha CM · 12 de junho de 2019

Olá à todos! Tenho esse trabalho de linguagem C para entregar na faculdade e estou com bastante dificuldade. Eu sei que devo utilizar operações básicas de vetores e matrizes, mas não sei como encaixar e qual a ordem correta do fluxo. Se alguém puder me dar uma mão, me orientando sobre o fluxo do programa - uma espécie de receita de bolo (como acredito que seja todo programa em C), ficarei bastante agradecida. No pdf existem inclusive algumas saídas esperadas e dicas de comandos a serem utilizados. Eu sou estupidamente burra sobre lógica de programação e me enrolo toda sobre a ordem das funções, quais ferramentas utilizar para matar o problema e etc. Aprecio qualquer luz.

Obrigada.

trabalho.pdf

Danizinha CM · 12 de junho de 2019

@KXSY Eu uso o Codeblocks. "Malloc" não posso utilizar, infelizmente.

Danizinha CM · 12 de junho de 2019

@KXSY Haha, eu te avisei que eu sou uma completa iniciante em C. Me perdoe, mas não entendi nada do seu código. Vou respirar aqui e tentar entender novamente. Agradeço imensamente seu esforço em me ajudar.

Danizinha CM · 13 de junho de 2019

@KXSY Eu tirei 0.3 na P1 e 1.8 na P2 da faculdade. Acredite, nesse fim de semestre já está sendo um inferno na terra. Mal consigo sequer dormir direito. Vou dar uma olhada querido, muito obrigada pela sua força. Infelizmente, pra quem não sabia absolutamente nada de C, já chegar em vetores e matrizes em pouquíssimo tempo, com mil outras matérias pesadíssimas pra estudar, tem sido muito desgastante. Eu tento conciliar o básico que sei, meio que traduzindo o possível para o "português" - se assim posso dizer, para tentar pegar o fluxo...

isrnick · 13 de junho de 2019

Eu fiz um campo minado um tempo atrás, até postei aqui no fórum na resposta em um tópico que o autor também postou outro código de campo minado:

Mas usei uma lógica diferente da proposta no enunciado do seu trabalho, não marca os campos como possíveis minas por exemplo.

Danizinha CM · 13 de junho de 2019

@isrnick Oi isrnick! Obrigada pela mensagem, vou dar uma olhadinha e ver se consigo extrair algo que me ajude. Obrigada!!!

Danizinha CM · 13 de junho de 2019

Alguém mais poderia dar uma luz?

arfneto · 14 de junho de 2019

9 horas atrás, Daniela Calfat Maldaun disse:

Alguém mais poderia dar uma luz?

Olá!

Meu palpite, com umas perguntas.

Acho que esse não deve ser seu primeiro ou segundo programa em C, ou em qualquer outra linguagem. Em geral os caras guardam esses problemas para entregar em período, depois de fazer outros programas menores. É esse o caso? Já escreveu um certo número de pequenos programas para se acostumar com o fluxo dessas coisas? Não o do programa em si, mas compilar, separar as coisas, testar, ler valores do teclado ou de arquivos, escrever na tela ou em arquivos?
Ajudaria saber o que você já sabe, para não ficar escrevendo coisas chatas ou redundantes e nem ficar, por outro lado, escrevendo o que você não entende ainda.

Li seu "requerimento", o arquivo. Está bem escrito.

A minha primeira sugestão: se você não conhece o jogo, jogue um pouco até ter a mecânica dele clara. Não se preocupe em programar p$%%@ nenhuma, apenas no jogo. Ganhar, perder, a rotina.

Depois: pense só no jogo também, mas nesse sentido: você e mais um jogador. Você tem umas folhas com um tabuleiro, tipo 3x3 só pra pensar. e você vai ter um pra você com as minas, tipo 2 minas só em 9 posições. E na mesa na sua frente seu amigo vai jogar: então você marca as minas num tabuleiro que você guarda. E dá um formulário tabuleiro pra ele. Ele vai jogando começa marcando as posições falando pra você que diz pra ele se acertou em algo e vai atualizando o tabuleiro.

Aí você está mais em condições de programar o serviço, depois de ter jogados umas vezes e de ter pensado nessa simulação com um amigo que pode ser você mesma...

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

fluxo do programa - uma espécie de receita de bolo (como acredito que seja todo programa em C)

Receitas de bolo podem ser bem complexas...

E a partir daí você pensa em escrever pequenas partes do serviço, partes que possa testar em separado e ir se acostumando com o problema e com os métodos de solução. Ex:

- uma função de desenha um tabuleiro de um certo tamanho

- uma função que faz o sorteio da posição das minas

- uma função que atualiza o tabuleiro

Coisas assim que possa testar em separado e possa por exemplo postar aqui e perguntar algo.

Assim vai se aproximando da solução. Esse é um programa relativamente grande para você começar pensando nele todo sem experiência..

Bom trabalho

Danizinha CM · 14 de junho de 2019

@arfneto Olá! Obrigada por sua mensagem! Sim, eu já fiz dois outros programas: o primeiro era bem simples - com menos de 20 linhas - sobre laços de repetição; o segundo sobre funções e como chamá-las. Para esse terceiro programa, o salto de dificuldade foi enorme, e em um período letivo de cerca de 22 dias. Essa dinâmica do jogo a qual você se refere, como ele funciona e etc, é exatamente o que eu venho tentando fazer nos últimos dias.

arfneto · 14 de junho de 2019

1 hora atrás, Daniela Calfat Maldaun disse:

@arfneto Olá! Obrigada por sua mensagem! Sim, eu já fiz dois outros programas: o primeiro era bem simples - com menos de 20 linhas - sobre laços de repetição; o segundo sobre funções e como chamá-las. Para esse terceiro programa, o salto de dificuldade foi enorme, e em um período letivo de cerca de 22 dias. Essa dinâmica do jogo a qual você se refere, como ele funciona e etc, é exatamente o que eu venho tentando fazer nos últimos dias.

Entendo.

Acho sacanagem esperar que um aluno se vire pra fazer um terceiro programa assim. Espero que tenha um bom prazo, mas não quero que desanime. O primeiro programa deve ter te dado essa noção de "receita de bolo", imagino

2 horas atrás, Daniela Calfat Maldaun disse:

exatamente o que eu venho tentando fazer nos últimos dias

Perfeito. Mas conhece campo minado? tem em seu computador? Jogou mesmo? Ganhou, perdeu e tal? É muito importante isso. E aquela parada de que falei de preparar o jogo para alguém é importante. Se ficar sem graça de fazer com alguém pode fazer com você mesma, no papel. Podia mandar pra mim mas ia levar dias pra jogar.

Sério, preparar o mapa, mesmo que 3x3, acompanhar os resultados de cada palpite, atualizar o mapa, preparar o tabuleiro. Fazendo isso umas vezes vai ajudar muito a entender a dinâmica disso.

Acho que a parte mais delicada é quando o sujeito seleciona uma célula vazia e aí você, como a controladora do jogo ou o seu programa, tem que ir abrindo as células em volta da célula vazia que o cara escolheu, e a área vazia vai se espalhando. Sabe mesmo como é isso? Não? Jogue! É de graça. Até entender claramente. Tem na loja do Windows 10 por exemplo. Vi agora.

Nunca pensei em programar isso, mas pode ser um exercício interessante. Mas repito: não tente fazer tudo ao mesmo tempo, ver o programa como uma coisa só. Não é e você vai perder um tempo enorme se fizer isso.

Pense no seu segundo programa, o das funções. Vai ser essencial. Pense na parte do "sorteio" das minas, veja se está claro como faz pra selecionar os campos, faça um pequeno programa de teste.

Pense na entrada, como seria a chamada do programa. Codifique uma função main() pra pegar os valores e mostrar na tela, só isso.

E irá progredindo rápido. C é uma linguagem bem legal, eu acho. Quando se sentir criativa, escolhendo maneiras de fazer ao invés de lutar pra achar uma, talvez goste mais de programar, ou odeie menos.... E pode nem demorar

Bom trabalho

Danizinha CM · 14 de junho de 2019

@arfneto Obrigada por sua mensagem, e pelas dicas. Infelizmente meu prazo está curtíssimo, tenho 2 dias para entregar o trabalho. O jogo campo minado em si é muito bacana e de fácil entendimento, mas há peculiaridades no enunciado pedido que acredito que faça com que seja uma variação não-usual do programa que estamos acostumados a ver no windows e afins. E converter isso em código realmente tem sido difícil pra mim. Mas não vou desistir, estou aqui tentando desenvolver o que posso, vendo aulas no youtube e etc. Estou longe de terminar, mas estou tentando ao menos. Agradeço pelo incentivo @arfneto, muito obrigada!!

arfneto · 14 de junho de 2019

6 minutos atrás, Daniela Calfat Maldaun disse:

@arfneto Obrigada por sua mensagem, e pelas dicas. Infelizmente meu prazo está curtíssimo, tenho 2 dias para entregar o trabalho. O jogo campo minado em si é muito bacana e de fácil entendimento, mas há peculiaridades no enunciado pedido que acredito que faça com que seja uma variação não-usual do programa que estamos acostumados a ver no windows e afins. E converter isso em código realmente tem sido difícil pra mim. Mas não vou desistir, estou aqui tentando desenvolver o que posso, vendo aulas no youtube e etc. Estou longe de terminar, mas estou tentando ao menos. Agradeço pelo incentivo @arfneto, muito obrigada!!

Li o enunciado. A única variação do usual --- ok, não jogo isso há eras --- acho que é a possibilidade de marcas as células suspeitas, ou desmarcar. Ou já tinha e eu nem sabia e marcava num papel . Mas isso não é nada complexo, basta acrescentar um estado a mais para as células e controlar o total de células marcadas para não estourar o limite.

Programe a entrada em separado, a parte do programa que pega os valores e faz a validação. E teste. E guarde. Você já fez bolo de festa? É algo assim tem o recheio, a cobertura a massa, a decoração... Espero que não fique brava com as analogia bestas... Mas abstração é importante na programação...

Vai ter trabalho para terminar isso em dois dias, em especial se não puder dispor de muito tempo só pra esse programa.
Para não perder tempo, já que o jogo aparentemente é familiar para você, escreva um programa que lê os valores do usuário, linhas, colunas, semente e tal. E valida e mostra na tela. Guarde.
Pense numa estrutura de dados para gravar isso, pode ser mesmo o simples m*n células, z minas e cada célula tem um estado, como no enunciado: marcado, desmarcado, aberto. Talvez marcado com mina e marcado sem mina, que tal? assim não precisa marcar as minas em outro lugar...

Se a sua estrutura se chamar Grade pode escrever algo assim

 struct Grade * define_grade(short m, short n, short z);

que cria uma grade e devolve pro seu programa. Entende isso? Já devolve a grade populada com as minas e com os estados das células ok.

Pense em uma definição para Grade que descreva bem o problema. Nem mais nem menos. Um dia isso foi um jogo de tabuleiro, onde você recebia continhas coloridas pra marcar as minas e pinos coloridos para marcas os resultaos, e jogava um contra o outro. Tinha a versão da batalha naval e mais mil variantes...

Saberia escrever esses dois?

Danizinha CM · 14 de junho de 2019

@arfneto

Estava tentando ao menos imprimir a primeira tabela, com uma matriz, igual existe no enunciado, mas não tive sucesso ainda, a saída me mostra números aleatórios sem sentido. Basicamente estou tentando seguir o enunciado e desbravando as coisas aos poucos, por mais complicado que seja.

isrnick · 14 de junho de 2019

10 minutos atrás, Daniela Calfat Maldaun disse:

mas há peculiaridades no enunciado pedido que acredito que faça com que seja uma variação não-usual do programa que estamos acostumados a ver no windows e afins.

A funcionalidade do jogo no Windows me parece ser a mesma da proposta no enunciado. No campo minado do Windows você deve clicar com o botão direito do mouse para marcar uma posição com a bandeira onde acha que tem uma mina, aí não tem risco de clicar por engano e detonar a mina marcada, porque não dá pra clicar na casa marcada, e também vai subtraindo do número de minas ainda não descobertas.

15 minutos atrás, arfneto disse:

A única variação do usual --- ok, não jogo isso há eras --- acho que é a possibilidade de marcas as células suspeitas, ou desmarcar. Ou já tinha e eu nem sabia e marcava num papel

Sempre funcionou assim mas é normal não saber, a muita gente que já jogou não sabe.

arfneto · 14 de junho de 2019

36 minutos atrás, Daniela Calfat Maldaun disse:

int tabuleiro[m][n];

Declare o tabuleiro com o tamanho maximo mesmo. No seu código você controla o que o sujeito digitou. 90x90 nem é grande assim.

Danizinha CM · 14 de junho de 2019

@arfneto E como eu controlo para aparecer o tabuleiro apenas com os dados inseridos pelo usuário?

adicionado 1 minuto depois

@arfneto você viu o enunciado? Aparece um tabuleiro com tamanho definido pelo usuário.

isrnick · 14 de junho de 2019

4 minutos atrás, Daniela Calfat Maldaun disse:

@arfneto E como eu controlo para aparecer o tabuleiro apenas com os dados inseridos pelo usuário?

adicionado 1 minuto depois

@arfneto você viu o enunciado? Aparece um tabuleiro com tamanho definido pelo usuário.

A ideia do @arfneto seria ter uma matriz de tamanho 90x90 na memória mas só usar uma parte dela, ou seja usar a parte que interessa para as dimensões escolhidas pelo usuário.

arfneto · 14 de junho de 2019

7 minutos atrás, Daniela Calfat Maldaun disse:

@arfneto E como eu controlo para aparecer o tabuleiro apenas com os dados inseridos pelo usuário?

adicionado 1 minuto depois

@arfneto você viu o enunciado? Aparece um tabuleiro com tamanho definido pelo usuário.

Sim.

No seu teste, coloque um valor fixo para as celulas do tabuleiro, para saber ideia se vai imprimir ok depois, algo como

10 * linha + coluna. E use um espaço depois onde imprime tabuleiro[m][n] para não ficar tudo grudado.

E esta salvando m e n para depois usar como indice no for. Porque nao escrever direto usando os indices i e j por exemplo?

isrnick · 14 de junho de 2019

Só como uma observação sobre o enunciado do trabalho:

O problema do enunciado é como ele propõe marcar as minas usando apenas rand(), mas não diz o que fazer se sortear uma posição onde já havia colocado uma mina anteriormente, nesse caso teria que sortear novamente até achar uma posição sem mina, mas aí tem o outro problema de ficar em loop infinito quando tiver um número grande de minas e o programa ficar sorteando milhares de vezes sem nunca achar uma casa vazia até travar.

Desse jeito, na situação que tiver um campo minado de 90 por 90 e 8099 minas (=90*90-1), por exemplo, é certeza que o programa vai travar, mas vamos assumir que o usuário sempre escolhe um número baixo de minas em relação ao tamanho do campo minado...

(Se quiser ver um método melhor depois veja como implementei no meu campo minado. Usei um algoritmo que pega um vetor com os números das posições do campo em sequencia (de 1 até m*n) e embaralhar os números aleatoriamente no vetor, e então as posições do campo que recebem as minas serão as posições dos z primeiros números do vetor embaralhado.)

Danizinha CM · 14 de junho de 2019

@arfneto Eu nao entendi muito bem como fazer. Olhando o enunciado, me parece que os indices i, j serão utilizados posteriormente para os “chutes” do usuario.

adicionado 4 minutos depois

Obrigada @isrnick @arfneto , vou reler as dicas e ver o que consigo fazer no código. Obrigada pela gentileza de vocês!

arfneto · 14 de junho de 2019

leia esse com atencao. E quase igual

	//
	// em uso estão mxn celulas apenas
	//
	for (i = 0; i < m; i++)
	{
		// m linhas
		for (j = 0; j < n; j++)
		{
			// colunas
			tabuleiro[i][j] = j + 10 * i; // pra saber o que esperar
		}
	}	// gravou um tabuleiro de teste

	// agora mostra
	for (i = 0; i < m; i++)
	{
		// m linhas
		for ( j = 0; j < n; j++)
		{
			// imprime [m][n]
			printf("%4i ", tabuleiro[i][j]);
		}
		printf("\n)");
	}

Vai imprimir assim:

Entende o que quero dizer como preencher com algo conhecido pra ver se está indo ok?

adicionado 28 minutos depois

14 minutos atrás, isrnick disse:

O problema do enunciado é como ele propõe marcar as minas usando apenas rand(), mas não diz o que fazer se sortear uma posição onde já havia colocado uma mina anteriormente, nesse caso teria que sortear novamente até achar uma posição sem mina, mas aí tem o outro problema de ficar em loop infinito quando tiver um número grande de minas e o programa ficar sorteando milhares de vezes sem nunca achar uma casa vazia até travar.

Desse jeito, na situação que tiver um campo minado de 90 por 90 e 8099 minas (=90*90-1), por exemplo, é certeza que o programa vai travar, mas vamos assumir que o usuário sempre escolhe um número baixo de minas em relação ao tamanho do campo minado

@isrnick

Essa é uma pegadinha clássica. Acho que o que se procura nesse exercício é ver se o aluno resiste à tentação de implementar sem pensar. Com esse número máximo de minas e os computadores de hoje em dia, vai ser zero eficiente mas vai levar uns segundos a mais talvez. Mas você tem razão: não é esperto fazer assim.

Essa situação é comum nos jogos de cartas para embaralhar antes de dar cartas de novo.

Um procedimento eficiente e seguro: imagine que você tem que colocar as 8099 minas em um tabuleiro de 8100 como falou: quando for colocar a ultima terá duas posições vazias e terá que escolher uma delas para colocar a última mina.

Mas no início terá 8100 casinhas livres para colocar sua próxima mina... Então como preencher o tabuleiro com exatas 8099 chamadas a rand()? Simples: veja o tabuleiro como uma longa fila de 8100 casinhas: no fundo é isso mesmo, certo?

Use rand() e sorteie a posicao da primeira mina. Agora voce tem 8099 possibilidades para colocar a proxima das 8098 minas restantes, certo? entao usa rand() e escolhe uma posicao nova, mas dessa vez entre 1 e 8099, ja que uma mina já está lá.

E assim por diante, até restar uma mina e duas casinhas livres.

Como colocar a mina no tabuleiro? Simples: pegue a posicao sorteada e conte de um em um a partir da primeira, mas obviamente pulando as posições onde ja tem mina, que nesse caso valem -1, pelo que vi.

Acho que entendeu já, mas na prática:

você usa um loop variando o total de minas a colocar. No inicio tem as z minas do enunciado. a cada passo no loop voce escolhe 1 mina entre as posições restantes, que serao o tamanho do tabuleiro menos o total de minas que ja estão la.

E aí cola ela na posicao sorteada, pulando as celulas que ja tem minas. Assim garante matematicamente o total de chamadas a rand() e evita a degradação dos tempos de execução conforme o tabuleiro vai ficando cheio... O total de "sorteios" fica constante: igual ao numero de minas, z

isrnick · 14 de junho de 2019

Precisa de 2 matrizes para o tabuleiro, uma para guardar valores de -1 até 8 (-1 se tiver mina e 0 a 8 nas demais posições dependendo do número de minas ao redor), e outra matriz para guardar o estado da casa fechado, aberto ou marcado (pode ser com números correspondentes 0, 1 e 2 respectivamente por exemplo).

Um passo a passo básico da lógica do programa:

0- Entrada de dados pelo usuário

1- Preencher as 2 matrizes com valores 0 para inicializá-las.

2- Na matriz de valores sortear z posições e colocar -1 indicando as posições que possuem uma mina.

3- Percorrer a matriz de valores colocando um número de 0 a 8 nas casas sem minas dependendo da quantidade de minas ao redor de cada uma delas.

4- Fazer o loop que fica imprimindo o tabuleiro e pedindo para o usuário digitar a próxima jogada até uma das condições de fim de jogo aconteça, o que é impresso no campo depende do que está aberto (imprime valor da casa ou minas estouradas), fechado (imprime . ) ou marcado (imprime * ) na matriz de estados.

5- Fazer a lógica de abertura ou marcação e desmarcação de casas mudando a matriz de estados adequadamente.

(Precisa fazer uma função recursiva para fazer a abertura automática das casas ao redor de casas abertas com valor 0, essa talvez seja a parte mais complicada, então primeiro faça normal abrindo só 1 casa mesmo nesse caso para pelo menos ter um jogo funcional salva em um arquivo separado, antes de tentar fazer isso.)

adicionado 12 minutos depois

@arfneto Sim, isso é o que o algoritmo de embaralhamento (Fisher-Yates ou Knuth shuffle) que mencionei faz, dei a explicação embaralhando o vetor de posições inteiro para facilitar a compreensão e implementação da lógica, mas poderia realizar apenas z operações de embaralhamento para obter z posições.

Danizinha CM · 14 de junho de 2019

@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 · 19 de junho de 2019

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 · 19 de junho de 2019

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;
}