Comunidad PHPeros

Otros => Los Retos PHPeros => Mensaje iniciado por: good en 13 de Agosto de 2011, 21:46:14 pm

Título: [Reto] Backtracking 1 (Con solución c++)
Publicado por: good en 13 de Agosto de 2011, 21:46:14 pm

Hola,

Lo que hay que hacer es generar todas las combinaciones posibles de 0 y 1 de longitud n, para una n dada.

Entrada:

Un número entero con el valor de n

Salida:

Todas las combinaciones de 0 y 1 de longitus igual a n;

---

Ejemplo de entrada:

3

Ejemeplo de salida:

000
001
010
011
100
101
110
100

---

Se tiene que resolver mediante backtracking (http://en.wikipedia.org/wiki/Backtracking (http://en.wikipedia.org/wiki/Backtracking))

---

fuente: olimpiada informática española

---

Solución posible: (c++)

Código: [Seleccionar]

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> VI;

void imprime_vector (VI& v) {
for (int i = 0; i < int(v.size()); ++i) cout << v[i];
cout << endl;
}

void combinaciones (int count, VI& v) {
if (int(v.size()) == count) {
imprime_vector(v);
return;
}
v[count] = 0;
combinaciones(count+1, v);
v[count] = 1;
combinaciones(count+1, v);
}

int main () {
int n;
cin>>n;
VI v(n);
combinaciones(0, v);
}

Título: Re:[Reto] Backtracking 1 (Con solución c++)
Publicado por: Physlet en 15 de Agosto de 2011, 18:42:59 pm

No es por nada pero... No te estás explicando nada en los enunciados de estos retos.
Apenas estoy comenzando el estudio de los grafos, pero de igual forma este enunciado no explica nada.

Saludos.

Título: Re:[Reto] Backtracking 1 (Con solución c++)
Publicado por: good en 25 de Agosto de 2011, 21:25:54 pm

Cita de: Physlet en 15 de Agosto de 2011, 18:42:59 pm

No es por nada pero... No te estás explicando nada en los enunciados de estos retos.
Apenas estoy comenzando el estudio de los grafos, pero de igual forma este enunciado no explica nada.

Saludos.

no hay nada que explicar... combinaciones, lo pillas? xDD

Título: Re:[Reto] Backtracking 1 (Con solución c++)
Publicado por: tuadmin en 19 de Octubre de 2011, 22:54:11 pm

me pillo la tarde jeje y no termine todo el codigo pero creo que que con esto se resuelve

Código: [Seleccionar]

<?php
error_reporting(E_ALL);
//variable que contiene las figuras
$combinacion = array(
array("0","1"),
array("0","1"),
array("0","1")
);
//los switchs que marcan la posicion de las figuras
$switchs = array(0,0,0);
//el conteo para cada figura segun la posicion y total de las mismas
$conteo = array(4,2,1);
$temporal = $conteo;
//for del total de las filas
for($i = 0;$i < array_product($conteo);$i++)
{
//for del total de las columnas
for($c = 0 ;$c < count($conteo) ;$c++)
{

//if($c==2){echo $switchs[$c];}
$figura = $combinacion[$c][$switchs[$c]];
echo $figura;
$temporal[$c]--;
if($temporal[$c] == 0){$switchs[$c]++;}
if($temporal[$c] <= 0 ){ $temporal[$c] = $conteo[$c];}
if($switchs[$c] >= count($combinacion[$c]))
{$switchs[$c]=0;}
}
echo "\n";
}
?>
segun mi teoria este codigo deberia poder no solo de combinar 0 y 1 si cualquier cantidad de simbolos
bueno pero por ahora lo lo tengo terminado asi que en otra lo acabo sie s q me acuerdo jeje byeeeee

Título: Re:[Reto] Backtracking 1 (Con solución c++)
Publicado por: good en 20 de Octubre de 2011, 20:08:19 pm

Hola, tuadmin;

tu solución es estática, en el enunciado pone 3 como ejemplo, pero puede ser cualquier entero

Título: Re:[Reto] Backtracking 1 (Con solución c++)
Publicado por: tuadmin en 21 de Octubre de 2011, 00:30:41 am

Cita de: good en 20 de Octubre de 2011, 20:08:19 pm

Hola, tuadmin;

tu solución es estática, en el enunciado pone 3 como ejemplo, pero puede ser cualquier entero

ejje si es estatica , era una idea abstracta para resolver el problema
bueno resultado final seria este :)

Código: [Seleccionar]

class llenar_array
{
private $symbols = array(
array('0','1'),
array('a','b'),
array('p','q'),
);
private $result = array();
private $total=8;
private $repeticion_col=array(4,2,1);
public function __construct()
{
call_user_func_array(array($this,"setSymbol"),func_get_args());
$this->_llenar();
}
public function addSymbols()
{
call_user_func_array(array($this,"setSymbol"),func_get_args());
$this->_llenar();
}
private function setSymbol()
{
$symbols = func_get_args();
if(!empty($symbols))
{
$this->symbols = func_get_args();
$this->repeticion_col=array();
}
}
private function _total()
{
$this->total = 1;
foreach($this->symbols as $col)
{
$this->total = $this->total * count($col);
}
}
private function _repeticion_col()
{
$total = 1;
$index = count( $this->symbols) - 1;
$this->repeticion_col[$index] = 1;
var_dump($this->symbols);
for($i =  $index-1;$i > -1;$i-- )
{
$total = count($this->symbols[$index]) * $total;
$this->repeticion_col[$i] = $total;
$index--;
}
}
private function _llenar()
{
$this->_repeticion_col();
$this->_total();
ksort($this->repeticion_col);
foreach($this->repeticion_col as $column=>$rep)
{
$this->_llenar_col($column,$rep);
}
}
private function _llenar_col($columna=0,$repeticion_por_array)
{
$incremento=0;
for($i=0;$i < $this->total ;$i++)
{
$index = ceil(($incremento+1)/$repeticion_por_array)-1;
if(!isset($this->symbols[$columna][$index]))
{
$incremento=0;
$index = ceil(($incremento+1)/$repeticion_por_array)-1;
}
$this->result[$i][$columna] = $this->symbols[$columna][$index];
$incremento++;
}
}
public function dump()
{
var_dump($this->result);
}
public function getRows()
{
return $this->result;
}
}
$llenar = new llenar_array(
str_split('01'),
str_split('01'),
str_split('01')
);
foreach($llenar->getRows() as $row)
{
foreach($row as $symbol)
{
echo $symbol;
}
echo "\n";
}


Título: Re:[Reto] Backtracking 1 (Con solución php)
Publicado por: tuadmin en 21 de Octubre de 2011, 00:47:50 am

bueno el resultado final despues de 6 horas de trabajo 2 cafes una hamburguesa y una llamada de mi ex
dieron el resultado final
clase.tuadmin.backtracking.php

Código: [Seleccionar]

<?php
//clase.tuadmin.backtracking.php
class tuadmin_backtracking_1
{
private $symbols = array(
array(&#39;0&#39;,&#39;1&#39;),
array(&#39;a&#39;,&#39;b&#39;),
array(&#39;p&#39;,&#39;q&#39;),
);
private $result = array();
private $total=8;
private $repeticion_col=array(4,2,1);
public function __construct()
{
call_user_func_array(array($this,"setSymbol"),func_get_args());
$this->_llenar();
}
public function addSymbols()
{
call_user_func_array(array($this,"setSymbol"),func_get_args());
$this->_llenar();
}
private function setSymbol()
{
$symbols = func_get_args();
if(!empty($symbols))
{
$this->symbols = func_get_args();
$this->repeticion_col=array();
}
}
private function _total()
{
$this->total = 1;
foreach($this->symbols as $col)
{
$this->total = $this->total * count($col);
}
}
private function _repeticion_col()
{
$total = 1;
$index = count( $this->symbols) - 1;
$this->repeticion_col[$index] = 1;
for($i =  $index-1;$i > -1;$i-- )
{
$total = count($this->symbols[$index]) * $total;
$this->repeticion_col[$i] = $total;
$index--;
}
}
private function _llenar()
{
$this->_repeticion_col();
$this->_total();
ksort($this->repeticion_col);
foreach($this->repeticion_col as $column=>$rep)
{
$this->_llenar_col($column,$rep);
}
}
private function _llenar_col($columna=0,$repeticion_por_array)
{
$incremento=0;
for($i=0;$i < $this->total ;$i++)
{
$index = ceil(($incremento+1)/$repeticion_por_array)-1;
if(!isset($this->symbols[$columna][$index]))
{
$incremento=0;
$index = ceil(($incremento+1)/$repeticion_por_array)-1;
}
$this->result[$i][$columna] = $this->symbols[$columna][$index];
$incremento++;
}
}
public function dump()
{
var_dump($this->result);
}
public function getRows()
{
return $this->result;
}
}
?>
Resolucion del problema

Código: [Seleccionar]

<?php
error_reporting(E_ALL);
require (&#39;clase.tuadmin.backtracking.php&#39;);
//creamos un pequeño proceso para las columnas de 0 y 1
do
{
$numero =(int) stream_get_line(STDIN,128);
}
while(ceil($numero) < 3);
$simbolos = array();
for($i = 0;$i < $numero;$i++)
{
$simbolos[] = str_split(&#39;01&#39;);
}

$llenar = new tuadmin_backtracking_1();
call_user_func_array(array($llenar,&#39;addSymbols&#39;),$simbolos);
foreach($llenar->getRows() as $row)
{
foreach($row as $symbol)
{
echo $symbol;
}
echo "\n";
}
bueno tengan buen tarde