Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales
Autor
|
Tema: Retos C/C++ (Leído 13,290 veces)
|
[L]ord [R]NA
Desconectado
Mensajes: 1.507
El Dictador y Verdugo de H-Sec
|
Bueno, esta zona esta un poco muerta por lo tanto no cuesta nada tratar de revivirla.
Tomando las mismas reglas que la del pasado post de retos de Python que se hizo en esta zona haremos uno en C/C++.
Reglas:
1) Se empezara con un ejercicio, quien lo resuelva propone otro ejercicio y asi seguimos. 2) Los ejercicios tendran un tiempo de vida de 3 dias, si en exactamente 3 dias alguien no publica una solucion alguien podra proponer otro ejercicio. 3) No publicar para decir cosas que no tengan que ver con la solucion al reto o para postear un nuevo reto. 4) Numerar los retos (Ej. Reto#1)
Bueno ya que yo postee, seria de mala educacion dejar que otro ponga el reto.
Reto#1: Realizar un programa que reciba un numero como argumento y diga si es primo o no.
PData: No estoy estudiando C/C++ actualmente en la universidad... (Para los que diran que es una tarea.)
|
|
|
|
|
En línea
|
|
|
|
Og.
Desconectado
Mensajes: 819
Aprendiendo de la vida
|
Se me paso lo de la entrada por argumento XD Editado... #include <iostream> using std::cout; using std::endl; int getNum(char* text) { int a=0, cont=0; while(text[cont]) { a *= 10; a += text[cont++] - '0'; } return a; } int main(int argc, char** argv) { int num; num = getNum(argv[1]); for(int i=2;i<=num/2;i++) if(!(num%i)) { cout << "No es primo" << endl; return 0; } cout << "Es primo" << endl; return 0; } Reto #2Realiza un programa que dado un numero n te imprima todas las posibles permutaciones del conjunto 1 a n ordenadas de menor a mayor. Ejemplo 1: Entrada 3 Salida 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Ejemplo 2: Entrada 4 Salida 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
|
|
|
|
« Última modificación: 19 Agosto 2010, 04:53 por Novlucker »
|
En línea
|
|-
|
|
|
Leyer
Desconectado
Mensajes: 772
[]
|
#include <iostream> #include <string> #include <sstream> using namespace std; void String(string a,string b); int main(int argc, char *argv[]) { string n=""; ostringstream stm; int value=0;cin>>value; for(int index=1;index<=value;index++){ stm<<index; n=stm.str(); }String("",n); return 0; } void String(string a, string b) { if(b.length() <= 1) cout<<a + b+"\n"; else for (int i = 0; i < b.length(); i++) { string n = b.substr(0, i) + b.substr(i + 1); String(a + b.at(i), n); } } Reto #3No me critiquen por lo fácil jaja XDDDD Generar esta matriz para un entero N dado: si se ingresa 4 1 0 0 0 0 1 2 0 0 0 1 2 3 0 0 1 2 3 4 0
|
|
|
|
« Última modificación: 19 Agosto 2010, 05:39 por LEYER »
|
En línea
|
|
|
|
Og.
Desconectado
Mensajes: 819
Aprendiendo de la vida
|
#include <iostream> using std::cin; using std::cout; using std::endl; int main(void) { int N; cin >> N; for(int i=0;i<N;i++) { for(int g=0; g<=i; g++) cout << g+1 << " "; for(int g=i; g<N; g++) cout << 0 << " "; cout << endl; } return 0; } Reto #4Dadas las denominaciones de monedas que tienen disponibles y una cantidad de dinero que tienen que dar de cambio con esas denominaciones de monedas (supongan que tienen una infinidad de monedas de cada denominacion y que siempre tienen monedas de $1) escriban un programa que regrese la cantidad MINIMA de monedas necesarias para regresar ese cambio, por ejemplo: {$1, $2, $5} y cambio de $9 la cantidad minima de monedas es 3 ($5 + $2 + $2 = $9) {$1, $5, $7} y cambio de $10 la cantidad minima de monedas es 2 ($5 + $5 = $10) por cierto, te puedo pedir el cambio de $3000 xD una ves que hagan este problema, muchos se darán cuenta de lo hermosa que es la resolución que le da nuestro cerebro a las cosas.
|
|
|
|
|
En línea
|
|-
|
|
|
|
|
Leo Gutiérrez.
. . .. ... ..... ........ ............. .....................
Colaborador
 
Desconectado
Mensajes: 2.968
/^$/
|
#include <iostream> #include <cstdlib> using std::cin; using std::cout; using std::endl; bool isperfect(const unsigned int& n) { unsigned int suma = 0; for(register unsigned int i = 1; i < n; i++) if(!(n % i)) suma += i; return(suma == n); } int main(int argc, char **argv) { if(argc != 2) exit(EXIT_FAILURE); for(register unsigned int i = 1; i <= atoi(*(argv + 1)); i++) if(isperfect(i) && (i < atoi(*(argv + 1)))) cout << i << endl; return 0; } Reto: Recorrer una matriz bidimensional con un puntero, con recorrer me refiero a mostrar cada uno de sus valores, no me refiero a indexación, sino a mostrar los valores usando aritmética de punteros.
|
|
|
|
« Última modificación: 19 Agosto 2010, 07:49 por Leo Gutiérrez. »
|
En línea
|
|
|
|
Og.
Desconectado
Mensajes: 819
Aprendiendo de la vida
|
no han resuelto el reto #4 XD por ejemplo yo te digo que las monedas que puedes dar son $1, $5 y $7, haora dime cual es la minima cantidad de monedas para completar la cantidad de 25$ Ejemplo1: Entrada 3 1 5 7 25 Salida 5 Ejemplo2: Entrada 1 1 25 Salida 25 el primer entero es el numero de denominaciones seguidas de n enteros que son los valores de las denominaciones y después el precio. devuelves simplemente el mínimo de monedas para lograr el precio. PD: es mas complejo de lo que parece, son esos problemas en los que te tienes que estar un par de horas pensando...
|
|
|
|
« Última modificación: 19 Agosto 2010, 08:06 por Og. »
|
En línea
|
|-
|
|
|
Leo Gutiérrez.
. . .. ... ..... ........ ............. .....................
Colaborador
 
Desconectado
Mensajes: 2.968
/^$/
|
PD: es mas complejo de lo que parece, son esos problemas en los que te tienes que estar un par de horas pensando...
Sí, jaja, es por eso que aún no respondemos :p
|
|
|
|
|
En línea
|
|
|
|
[L]ord [R]NA
Desconectado
Mensajes: 1.507
El Dictador y Verdugo de H-Sec
|
@Og.:Ni idea de que quieres en realidad, querias ver la cantidad minima de monedas para dar cambio y eso es que realiza el programa... ahora creo que estas re-planteando el problema variandolo.
|
|
|
|
|
En línea
|
|
|
|
Og.
Desconectado
Mensajes: 819
Aprendiendo de la vida
|
@Og.:Ni idea de que quieres en realidad, querias ver la cantidad minima de monedas para dar cambio y eso es que realiza el programa... ahora creo que estas re-planteando el problema variandolo.
Tal ves me di a malentender. En si no seria un reto si se usara el sistema de monedas que usamos cotidianamente, por que simplemente vas quitando la mayor denominación hasta que no puedas mas y empezar con la siguiente y asi sucesivamente, por eso lo del cambio de denominaciones. limitare un poco el problema, supondríamos que solo existen tres tipos de moneda: un peso, 5 pesos y 7 pesos nada mas. ahora has el mismo problema y veras por que empieza a agarrar complejidad XD el problema sera solo saber cual es el mínimo de monedas para llegar a un numero.
Bueno, con el de Leo: #include <iostream> using namespace std; int main(void) { int mat[5][5]; for(int i=0; i<5; i++) for(int g=0; g<5;g++) mat[i][g] = i*g; int* a = mat[0]; for(int i=0;i<25;i++) { if(!(i%5)) cout << endl; cout << *a++ << " "; } } te refieres a algo asi?
|
|
|
|
|
En línea
|
|-
|
|
|
Leo Gutiérrez.
. . .. ... ..... ........ ............. .....................
Colaborador
 
Desconectado
Mensajes: 2.968
/^$/
|
Sí, así es.
La idea es poner problemas sencillitos e ir aumentando la dificultad.
Saludos.
|
|
|
|
|
En línea
|
|
|
|
Oblivi0n
Desconectado
Mensajes: 201
Odio las ranas.
|
Buenas, yo me apunto a los retos, alguien puede decirme cuales estan resueltos y cuales no? (aunque los acabaré haciendo todos xD)
|
|
|
|
|
En línea
|
|
|
|
[L]ord [R]NA
Desconectado
Mensajes: 1.507
El Dictador y Verdugo de H-Sec
|
@guru6: las reglas... @Og.: Te falto dejar el proximo reto.
|
|
|
|
|
En línea
|
|
|
|
|
ghastlyX
|
Para el de las monedas, el problema surge en que el algoritmo greedy de ir cogiendo siempre las monedas más grandes no minimiza la cantidad de monedas, como se puede ver en el primer ejemplo que se ha puesto. Una posible solución correcta pero muy ineficiente sería un backtracking probando todas las posibles maneras. Una forma mejor, que dejo a continuación, sería usando programación dinámica, quedando entonces una complejidad polinómica, en concreto O(np), donde n es el número de monedas y p la cantidad. Quizá me haya equivocado en algo, pero creo que es correcto. #include <iostream> #include <vector> using namespace std; const int INF = 1000000000; int dp(int p, vector<int>& M, vector<int>& v) { if (p < 0) return INF; if (p == 0) return 0; //Caso base if (M[p] == -1) { M[p] = INF; for (int i = 0; i < v.size(); ++i) M[p] = min(M[p], 1 + dp(p - v[i], M, v)); } return M[p]; } int main() { int n, p; cin >> n; vector<int> v(n); for (int i = 0; i < n; ++i) cin >> v[i]; //Lectura de las monedas cin >> p; vector<int> M(p + 1, -1); //Tabla para la dinamica cout << dp(p, M, v) << endl; }
|
|
|
|
|
En línea
|
|
|
|
Og.
Desconectado
Mensajes: 819
Aprendiendo de la vida
|
@ghastlyX Bien!!
Te toca dejarnos un reto.
|
|
|
|
|
En línea
|
|-
|
|
|
|
|