90
edits
Changes
Jump to navigation
Jump to search
no edit summary
'''''nextstruct(it);'''''
pela qual nós podemos ver que esse iterador está usando a mesma lexicografia ordenando como usamos no algoritmo 3.
==='''6. Computações e explorações'''===
1. (Projetos de computador) Dado um inteiro positivo “n”, encontre a probabilidade de selecionar seis inteiros do conjunto {<math>1, \cdots , n</math>} que foram mecânicamente selecionados em uma loteria.
Solução
Nós seguiremos o exemplo 4 no texto. O número total de maneiras de escolher 6 números de “n” números é <math>C(n, 6)</math>, que pode ser encontrado com o procedimento “numbcomb” no pacote “combinat”. Isso nos dá o número total de possibilidades, onde apenas uma irá vencer.
'''''Lottery := proc(n::posint) '''''
'''''local total; '''''
''''' total := combinat[numbcomb](n, 6); '''''
''''' 1.0 / total; '''''
'''''end: '''''
'''''Lottery(49); '''''
Se as regras da loteria mudarem, para que o número de números escolhidos seja algo diferente de 6, então nós devemos modificar o procedimento acima. (Por exemplo, talvez agora possamos escolher 5 números de 499, em vez de 6.) Nós podemos facilmente modificar nosso programa para nos deixar especificar quantos números nós queremos escolher adicionando outro parâmetro.
'''''Lottery2 := proc(n::posint, k::posint) '''''
'''''local total; '''''
''''' total := combinat[numbcomb](n,k); '''''
''''' 1.0 / total; '''''
'''''end: '''''
'''''Lottery2(49,6); '''''
'''''Lottery(30,3); '''''
2. Dados inteiros positivos “n” e “r”, liste todas as r-combinações, com repetições permitidas, do conjunto .
Solução
A função “choose” do Maple (no pacote “combinat”), vai listar todas as r-combinações de, mas sem repetições. Portanto nós não podemos usá-la diretamente. Entretanto, digamos que queremos todas as 2-combinações de, com repetições.
Isso quer dizer que junto com , e , nós também queremos incluir, e . Nós queremos ser capazes de escolher cada número até 2 vezes. (Nós dizemos que podemos repetir um elemento qualquer número de vezes, mas na prática, já que nós apenas podemos escolher 2 coisas no total, nós só precisamos permitir cada número aparecer no máximo 2 vezes.) Então outra forma de olhar o problema é dizer que queremos todas as 2-combinações, sem repetição, do conjunto. Em geral, então, nós podemos encontrar todas as r-combinações de com repetição pedindo por todas as r-combinações, onde cada elemento aparece “r” vezes.
'''''RCombRepetition := proc(n::posint, r::posint) '''''
'''''local repeatlist, i; '''''
''''' repeatlist := [ seq( i $ r, i=1..n) ]; '''''
''''' combinat[choose](repeatlist, r); '''''
'''''end: '''''
'''''RCombRepetition(3,2); '''''
'''''RCombRepetition(4,3); '''''
(Notas sobre o procedimento: O “i $ r” significa repetir “i” r vezes.
'''''1 $ 3; '''''
'''''happy $ 4; '''''
Além disso, nós precisamos usar uma lista em vezes de um conjunto, já que o Maple automaticamente remove elementos repetidos em um conjunto e nós perderíamos todas as repetições.)
'''''happylist := [ happy $ 4]; '''''
'''''happyset := happy $ 4 ; '''''
3. Encontre o número de resultados possíveis em uma partida de dois times quando o vencedor é o primeiro time a ganhar 5 de 9, 6 de 11, 7 de 13 ou 8 de 15 jogos.
Solução
Nossa solução vai usar o procedimento Maple chamado “permute” para computar o número total de maneiras que um torneio de jogos pode ser jogado. Vamos começar construindo duas listas que observa como cada um dos dois times pode ganhar. Nós iremos atribuir as duas do time 1 vencendo o torneio sem nenhuma derrota, e o time 2 vencendo o torneio sem nenhuma derrota. A cada iteração do loop principal do algoritmo, vamos computar as permutações possíveis de jogos a serem jogados, notando que a ordem de vitórias é importante para nós. Após essas permutações serem calculadas, nós vamos aumentar o número de jogos que o torneio dura (ou seja, permite o eventual time perdedor do torneio a vencer um jogo adicional). Isso é equivalente a usar um diagrama de árvore para computar os resultados possíveis. O loop externo (while) corresponde ao nível de vértices na árvore, e o loop interior (for) itera sobre todos os jogos naquele nível.
A implementação Maple dessa descrição é mostrada abaixo.
'''''Tournaments:=proc(games::integer) '''''
''''' local i, one_wins, two_wins, Temp, S; '''''
Inicialize uma lista para garantir que o time 1 vença
''''' one_wins:=[seq(1, i=1..ceil(games/2))]; '''''
Inicialize uma lista para garantir que o time 2 vença
''''' two_wins:=[seq(2, i=1..ceil(games/2))]; '''''
''''' S:={}; '''''
Percorra até nós termos todos os jogos da série usados
''''' while nops(one_wins) <= games do '''''
Calcule os resultados possíveis que completam em jogos exatos
''''' Temp:=permute(one_wins); '''''
''''' for i from 1 to nops(Temp) do '''''
Garanta que nós realmente precisamos de todos os jogos (ou seja, o último jogo da série foi vencido pelo time 1)
''''' if Temp[i][nops(one_wins)] = 1 then '''''
''''' S:=S union Temp[i] '''''
''''' fi; '''''
''''' od; '''''
Calcule os resultados possíveis que completa em jogos exatos
''''' Temp:=permute(two_wins); '''''
''''' for i from 1 to nops(Temp) do '''''
Garanta que nós realmente precisamos de todos os jogos (ou seja, o último jogo da série foi vencido pelo time 2)
''''' if Temp[i][nops(two_wins)] = 2 then '''''
''''' S:=S union Temp[i] '''''
''''' fi; '''''
''''' od; '''''
Incremente o número de jogos, para que o time vencedor do torneio perca um jogo a mais.
''''' one_wins:=[op(one_wins), 2]; '''''
''''' two_wins:=[op(two_wins), 1]; '''''
''''' od; '''''
''''' S; '''''
'''''end: '''''
Agora nós usamos esse procedimento recentemente criado em torneios que são o melhor de “3-de-5” e o melhor de “4-de-7” em número de jogos.
'''''Tournaments(5); '''''
'''''nops(%); '''''
'''''nops(Tournaments(7)); '''''
Ao leitor é deixado explorar os casos restantes, e conjecturar uma fórmula no caso geral.
