Wikilibros

Diferencia entre revisiones de «El problema de la organización del calendario de un campeonato con Divide y Vencerás»

Explorar historial interactivamente
← Edición anteriorEdición siguiente →
Contenido eliminado Contenido añadido
VisualWikitexto
m código
Línea 52:
 
 
<font face="Arial, Helvetica, sans-serif"><strong> ==Caso b&aacute;sico:</strong></font> ===
seSe da cuando solo tenemos dos participantes. La soluci&oacute;n es inmediata puesto que competir&aacute;n entre ambos.
puesto que competir&aacute;n entre ambos.
 
===Caso recursivo===
<font face="Arial, Helvetica, sans-serif"><strong>Caso recursivo: </strong></font>
seSe da cuando tenemos m&aacute;s de dos participantes. Partiendo del problema de tama&ntilde;o 2<sup>k</sup> podemos subdividir el problema en dos: que vayan desde '''1''' a '''2<sup>k-1</sup>''' participantes, y el otro desde ''2<sup>k-1</sup>+1''' a '''2<sup>n</sup>''' participantes.
tama&ntilde;o 2<sup>k</sup> podemos subdividir el problema en dos: que vayan desde '''1''' a
'''2<sup>k-1</sup>''' participantes, y el otro desde '''2<sup>k-1</sup>+1''' a '''2<sup>n</sup>''' participantes.
La unión de los dos subresultados no da la solución final. Después de conseguirlas individualmente tendremos que combinarlas: Para ello habrá que cruzarlas puesto que faltan las competiciones de los participantes de la primera subsolución con los de la segunda. Se trata de que los participantes de la primera parte jueguen con los de la segunda y viceversa. Para formar el subcalendario del primer participante basta con que compita en días sucesivos con los participantes de numeración superior en orden creciente, es decir, sucesivamente con los participantes '''2<sup>k-1</sup>+1''',...,'''2<sup>n</sup>'''.
La unión de los dos subresultados no da la solución final.
Después de conseguirlas individualmente tendremos que combinarlas:
Para ello habrá que cruzarlas puesto que faltan las competiciones de los participantes de la primera subsolución
con los de la segunda.
Se trata de que los participantes de la primera parte jueguen con los de la segunda y viceversa. Para formar el
subcalendario del primer participante basta con que compita en días sucesivos con los participantes de numeración
superior en orden creciente, es decir, sucesivamente con los participantes '''2<sup>k-1</sup>+1''',...,'''2<sup>n</sup>'''.
El siguiente participante toma esta secuencia y realiza una permutación de la misma rotando dicha secuencia a la derecha. Este proceso se repite para el resto de los participantes de numeración inferior.
la derecha.
Este proceso se repite para el resto de los participantes de numeración inferior.
 
 
 
Línea 78 ⟶ 66:
 
<table width="36%" border="1">
<tr>
<td><p><font color="#8000FF"><strong>Caso b&aacute;sico:</strong></font></p>
<table width="9%" border="1">
<tr>
<td width="52%">&nbsp;</td>
<td width="48%"><strong><font color="#00FF00">1</font></strong></td>
</tr>
<tr>
<td><font color="#00FF00"><strong>1</strong></font></td>
<td><strong>2</strong></td>
</tr>
<tr>
<td><font color="#00FF00"><strong>2</strong></font></td>
<td><strong>1</strong></td>
</tr>
</table>
<p><font color="#8000FF"><strong>Caso recursivo:</strong></font></p>
<table width="40%" border="1">
<tr>
<td>&nbsp;</td>
<td><strong><font color="#00FF00">1</font></strong></td>
<td><strong><font color="#00FF00">2</font></strong></td>
<td><strong><font color="#00FF00">3</font></strong></td>
</tr>
<tr>
<td><strong><font color="#00FF00">1</font></strong></td>
<td><strong>2</strong></td>
<td><strong>3</strong></td>
<td><strong>4</strong></td>
</tr>
<tr>
<td><strong><font color="#00FF00">2</font></strong></td>
<td><strong>1</strong></td>
<td><strong>4</strong></td>
<td><strong>3</strong></td>
</tr>
<tr>
<td><strong><font color="#00FF00">3</font></strong></td>
<td><strong>4</strong></td>
<td><strong>1</strong></td>
<td><strong>2</strong></td>
</tr>
<tr>
<td><strong><font color="#00FF00">4</font></strong></td>
<td><strong>3</strong></td>
<td><strong>2</strong></td>
<td><strong>1</strong></td>
</tr>
</table>
</td>
</tr>
</table>
<p>&nbsp;</p>
Línea 135 ⟶ 123:
'''El resultado del calendario del campeonato es de la forma:'''
<table width="40%" border="1">
<tr>
<td><font size="3">&nbsp;</font></td>
<td><font color="#00FF00" size="3"><strong>1</strong></font></td>
<td><font color="#00FF00" size="3"><strong>2</strong></font></td>
<td><font color="#00FF00" size="3"><strong>3</strong></font></td>
<td><font color="#00FF00" size="3"><strong>4</strong></font></td>
<td><font color="#00FF00" size="3"><strong>5</strong></font></td>
<td><font color="#00FF00" size="3"><strong>6</strong></font></td>
<td><font color="#00FF00" size="3"><strong>7</strong></font></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">1</font></strong></td>
<td><strong><font color="#0000FF" size="3">2</font></strong></td>
<td><strong><font color="#0000FF" size="3">3</font></strong></td>
<td><strong><font color="#0000FF" size="3">4</font></strong></td>
<td><strong><font color="#000000" size="3">5</font></strong></td>
<td><font color="#FF0080" size="3"><strong>6</strong></font></td>
<td><font color="#FF0080" size="3"><strong>7</strong></font></td>
<td><font color="#FF0080" size="3"><strong>8</strong></font></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">2</font></strong></td>
<td><strong><font color="#0000FF" size="3">1</font></strong></td>
<td><strong><font color="#0000FF" size="3">4</font></strong></td>
<td><strong><font color="#0000FF" size="3">3</font></strong></td>
<td><strong><font color="#000000" size="3">8</font></strong></td>
<td><font color="#FF0080" size="3"><strong>5</strong></font></td>
<td><font color="#FF0080" size="3"><strong>6</strong></font></td>
<td><font color="#FF0080" size="3"><strong>7</strong></font></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">3</font></strong></td>
<td><strong><font color="#0000FF" size="3">4</font></strong></td>
<td><strong><font color="#0000FF" size="3">1</font></strong></td>
<td><strong><font color="#0000FF" size="3">2</font></strong></td>
<td><strong><font color="#000000" size="3">7</font></strong></td>
<td><font color="#FF0080" size="3"><strong>8</strong></font></td>
<td><font color="#FF0080" size="3"><strong>5</strong></font></td>
<td><font color="#FF0080" size="3"><strong>6</strong></font></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">4</font></strong></td>
<td><strong><font color="#0000FF" size="3">3</font></strong></td>
<td><strong><font color="#0000FF" size="3">2</font></strong></td>
<td><strong><font color="#0000FF" size="3">1</font></strong></td>
<td><strong><font color="#000000" size="3">6</font></strong></td>
<td><font color="#FF0080" size="3"><strong>7</strong></font></td>
<td><font color="#FF0080" size="3"><strong>8</strong></font></td>
<td><font color="#FF0080" size="3"><strong>5</strong></font></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">5</font></strong></td>
<td><strong><font color="#FF0080" size="3">6</font></strong></td>
<td><strong><font color="#FF0080" size="3">7</font></strong></td>
<td><strong><font color="#FF0080" size="3">8</font></strong></td>
<td><font color="#000000" size="3"><strong>1</strong></font></td>
<td><strong><font color="#0000FF" size="3">2</font></strong></td>
<td><strong><font color="#0000FF" size="3">3</font></strong></td>
<td><strong><font color="#0000FF" size="3">4</font></strong></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">6</font></strong></td>
<td><strong><font color="#FF0080" size="3">5</font></strong></td>
<td><strong><font color="#FF0080" size="3">8</font></strong></td>
<td><strong><font color="#FF0080" size="3">7</font></strong></td>
<td><font color="#000000" size="3"><strong>4</strong></font></td>
<td><strong><font color="#0000FF" size="3">1</font></strong></td>
<td><strong><font color="#0000FF" size="3">2</font></strong></td>
<td><strong><font color="#0000FF" size="3">3</font></strong></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">7</font></strong></td>
<td><strong><font color="#FF0080" size="3">8</font></strong></td>
<td><strong><font color="#FF0080" size="3">5</font></strong></td>
<td><strong><font color="#FF0080" size="3">6</font></strong></td>
<td><font color="#000000" size="3"><strong>3</strong></font></td>
<td><strong><font color="#0000FF" size="3">4</font></strong></td>
<td><strong><font color="#0000FF" size="3">1</font></strong></td>
<td><strong><font color="#0000FF" size="3">2</font></strong></td>
</tr>
<tr>
<td><strong><font color="#00FF40" size="3">8</font></strong></td>
<td><strong><font color="#FF0080" size="3">7</font></strong></td>
<td><strong><font color="#FF0080" size="3">6</font></strong></td>
<td><strong><font color="#FF0080" size="3">5</font></strong></td>
<td><font color="#000000" size="3"><strong>2</strong></font></td>
<td><strong><font color="#0000FF" size="3">3</font></strong></td>
<td><strong><font color="#0000FF" size="3">4</font></strong></td>
<td><strong><font color="#0000FF" size="3">1</font></strong></td>
</tr>
</table>
 
Línea 232 ⟶ 220:
'''tabla[participante,dia]=contrincante'''
 
<code>
 
'''Procedimiento''' formarTabla(ent/sal t: tabla; primero, ultimo:1..n)
'''var'''
Línea 255 ⟶ 243:
'''fsi'''
'''end'''
</code>
 
 
 
<code>
 
 
'''Procedimiento''' CompletarTabla(ent/sal t: tabla; eqInf, eqSup, díaInf, díaSup,eqInicial: 1..n)
'''begin'''
Línea 274 ⟶ 262:
'''fpara''';
'''end'''
</code>
 
 
 
'''Procedimiento principal que realiza la inicialización adecuada:'''
 
<code>
'''Procedimiento''' Calendario (ent/sal t: tabla)
'''begin'''
Línea 284 ⟶ 273:
formarTabla(t,1,n);
'''end'''
</code>
 
 
 
----
Algoritmo de DV
Obtenido de «https://es.wikibooks.org/wiki/El_problema_de_la_organización_del_calendario_de_un_campeonato_con_Divide_y_Vencerás»