La más eficiente sin tu último requerimiento sería esta:

function factorial ($numero){

return $numero == 1 ? $numero : $numero * factorial($numero - 1);
}

esta solución tardaría lo mismo que la anterior, puedes optimizar este mismo código para que sea mucho más eficiente

Hola Good,

Verás, no se si llegas a entenderme bien. A lo que yo voy es a decirte que por muy "eficaz" y rápida crees una función dará igual si la llamas 5000 veces. La función no sabe cuantas veces la está llamando por lo tanto no se puede hacer nada respecto a ello.

Si, visto de esa forma si que es mas corto de elaborar. Bien visto así Physlet, enhorabuena.

Un saludo,
Siquillote.

sigue siendo "ineficiente" en cuestión de rapidez

Hola Good,

La verdad no entiendo porque dices que no es lo suficientemente rápido... a mi ni me tarda milésimas. En cuanto a que dices que se puede optimizar yo creo que es "imposible". Se utilizan los métodos exactos y concisos, ni mas ni menos. Hombre, se podría simplificar quitando la función pero como tu pedías una función...

Un saludo,
Siquillote.

hay una manera de hacerlo más eficiente. Éste que has hecho funciona bien, sí, pero siempre tiene que realizar el cálculo completo, por ejemplo, si lo probaras así:

factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);
factorial (1000);

seguramente no sería tan rápido xD

hola! la idea es crear una función como por ejemplo factorial($n);, y que devuelva el factorial de n (n!)

A ver quien hace el procedimiento más rápido!!


El factorial de 3 es 1*2*3, el de 5 es 1*2*3*4*5... etc

NOTA EXTRA:
he pensado en limitar el número que se pase por input, la función solo procesa números del 0 al 15

Una solución posible (hay una manera más eficiente pero no la sé xD) es ésta:

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

typedef vector<vector<int> > VVI;
typedef vector<pair<int, int> > VPII;

bool se_puede (VVI& v, int xx, int y, int numero) {
for (int i = 0; i < 9; ++i) {
if (v[xx][i] == numero) return false;
else if (v[i][y] == numero) return false;
}

int fil = 3*(xx/3);
int col = 3*(y/3);
for (int i = fil; i < fil+3; ++i) {
for (int x = col; x < col+3; ++x) {
if (v[i][x] == numero) return false;
}
}
return true;
}

void backtrack (VVI& sudoku, VPII& pos, int count) {
if (count == pos.size()) {
for (int i = 0; i < 9; ++i) {
for (int x = 0; x < 8; ++x) cout << sudoku[i][x] << " ";
cout << sudoku[i][8];
cout << endl;
}
} else {
pair<int, int> p = pos[count];
int posX = p.first;
int posY = p.second;
for (int i = 0; i < 9; ++i) {
if (se_puede(sudoku, posX, posY, i+1)) {
sudoku[posX][posY] = i+1;
backtrack(sudoku, pos, count+1);
sudoku[posX][posY] = 0;
}
}
}
}

int main () {
VVI sudoku(9, vector<int>(9));
VPII blank;
for (int i = 0; i < 9; ++i) {
for (int x = 0; x < 9; ++x) {
cin>>sudoku[i][x];
if (sudoku[i][x] == 0) blank.push_back(make_pair(i, x));
}
}
backtrack(sudoku, blank, 0);
}
la función se_puede devuelve true sí un número (int numero) se puede poner en una casilla específica para un tablero dado.

Hola,

Podrías hacer un programa sencillo que resuelva un sueoku?

Entrada:

Un sudoku, 9 filas de 9 columnas cada una inidicando con 0 las casillas vacías.

Salida:

Una solución al sudoku pasado por la entrada

---

Ejemplo de entrada:

0 0 7 0 0 0 0 0 2
0 0 0 1 3 0 0 8 6
2 0 0 0 8 4 0 0 5
0 3 1 8 0 0 0 0 4
0 7 0 9 0 0 0 0 0
5 9 0 0 7 0 0 3 0
3 0 4 0 0 1 0 5 0
0 0 0 5 0 0 0 0 0
0 0 0 0 0 0 8 0 0

Ejemplo de Salida:

8 1 7 6 5 9 3 4 2
9 4 5 1 3 2 7 8 6
2 6 3 7 8 4 1 9 5
6 3 1 8 2 5 9 7 4
4 7 2 9 1 3 5 6 8
5 9 8 4 7 6 2 3 1
3 8 4 2 9 1 6 5 7
7 2 9 5 6 8 4 1 3
1 5 6 3 4 7 8 2 9

---

El truco de este problema es saber qué números se pueden poner, es decir, no sería eficiente probar todos los número [1,9] inclusive, el programa tardaría demasiado tiempo. Yo recomendaría hacer alguna(s) funciones para saber qué números pueden encajar en cada casilla (teniendo en cuenta la fila en la que estamos, la columna y el cuadrado de 3x3)

Fuente: Olimpiada informática española

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)

---

fuente: olimpiada informática española

---

Solución posible: (c++)

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