Mensajes

Hola, como sabran o se imaginaran, soy adicionado a la informatica, y en el libro todavia no he visto la función pow, asi que me preguntaba si  "num ^ exp" seria  valido para calcular la potencia de algun numero. saludoss

Ese operador es la XOR bit a bit. No hay un operador para calcular potencias en C, tienes que usar la función pow como ya te han dicho o hacerte una tú mismo.

Te dejo un código que calcula potencias usando Divide&Conquer con una complejidad de O(logn) (los que te han puesto son O(n)). Esto es útil sobretodo cuando se quieren calcular potencias muy grandes módulo un cierto número.

Código (c) [Seleccionar] Expandir

#include <stdio.h>

int eleva(int base, int exp) {
    if (exp == 0) return 1;
    int res = eleva(base, exp/2);
    res *= res;
    if (exp%2 == 1) res *= base;
    return res;
}

int main() {
    int base, exp;
    scanf("%d %d", &base, &exp);
    printf("%d\n", eleva(base, exp));
}

Sería mucho más eficiente si en lugar de iterar sobre los números, iteraras sobre el factor del 5, así pasarías directamente por los múltiplos.

Además, matemáticamente puedes resolverlo sin bucles. Pongo un programa que recoge en primer lugar el valor (en tu caso el 5) y a continuación el número de múltiplos que se quiera sumar e imprime su suma.

Código (c) [Seleccionar] Expandir

#include <stdio.h>

int main() {
    int valor, n;
    scanf("%d %d", &valor, &n);
    printf("%d\n", valor*n*(n + 1)/2);
}

Del problema de la mochila hay muchas variaciones y según entiendo de lo que dices, tú estás buscando resolver lo que se conoce como Fractional Knapsack Problem, mientras que el código que has puesto a simple vista parece que hace una DP para resolver el problema de la mochila estándar, donde los objetos no se pueden fraccionar (o se meten o no se meten).

En tu caso, el problema del Fractional Knapsack Problem, es mucho más simple y no requiere programación dinámica. Lo puedes resolver con un greedy muy tonto, ordenando lo objetos según beneficio/tamaño e ir cogiendo en orden los que tengan mayor cociente hasta llenar la mochila.

http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_anchura

Ahí lo tienes bastante bien explicado. Es un algoritmo de búsqueda en grafos. Para grafos cuyas aristas tengan todas el mismo coste, se puede usar para encontrar distancias mínimas de un nodo al resto.

Aparte que mirándolo por encima, parece que ese código intenta resolver el problema del Knight's Tour, no lo que tú necesitas. Inténtalo hacer tú mismo usando BFS que es muy sencillo.

O siquiera que busque antes de preguntar, puse un link a un codigo que habia visto aquí antes..! y aun así dice que no vale 

De todas maneras, el código que has puesto no hace lo que él necesita, simplemente muestra a donde puede ir el caballo dada una posición inicial. Además, ya puestos, ese código es horrible xDD.

Vaya chanchullos...

¿Desde cuándo va así este foro, que para recibir ayuda tienes que darla primero?

Para el problema del caballo, lo puedes resolver usando BFS (Búsqueda en anchura) y empezando en la casilla inicial. Si vas guardando el coste mínimo para llegar a cada casilla, obtendrás en concreto el que tú buscas. Hay una manera un poco más eficiente de hacerlo, pero es un poco más complicada y tampoco te quiero liar si no sabes hacerlo de la forma estándar. Intenta hacerlo y te vamos ayudando, lo que no vamos a hacer es darte el código, que programándolo bien se puede hacer en unas 30 línias así a ojo.

El primero puede hacerse bastante más corto haciéndolo recursivamente. No lo probado, pero deberían funcionar las dos funciones.

Código (java) [Seleccionar] Expandir

public class conversor {
    public static String decimalBase(long x, int base) {
        String res;
        if (x%base <= 9) res = new String(String.valueOf((char)(x%base + '0')));
        else res = new String(String.valueOf((char)(x%base - 10 + 'A')));
        if (x/base > 0) res = decimalBase(x/base, base).concat(res);
        return res;
    }

    public static long baseDecimal(String numero, long base) {
        long res = 0;
        for (int i = 0; i < numero.length(); ++i)
            res = res*base + (long)Character.getNumericValue(numero.charAt(i));
        return res;
    }
}

Siento si hay algo del código que no sea necesario, como por ejemplo castings. Java no es el lenguaje que uso habitualmente.

EDITO:
No había visto lo de en cualquier lenguaje. Pongo la primera función en C++ de una forma más compacta.

Código (cpp) [Seleccionar] Expandir

typedef long long ll;

string dtoB(ll x, int b) {
    return ((x/b > 0)?dtoB(x/b, b):"") + char(x%b + (x%b < 10)*'0' + (x%b >= 10)*('A' - 10));
}

El enunciado tiene muchas imprecisiones. Cuando dice la primera solución, entiendo que se refiere a la primera que encuentre el backtracking, pero no queda claro ni especifica qué criterio usar.

Lo segundo que pide es, bajo mi punto de vista, erróneo. Con el enunciado actual no se prohíben los ciclos, de forma que existen infinitos caminos para la gran mayoría de laberintos. Se tendría que especificar una longitud máxima o bien exigir que no haya ciclos.

Lo tercero es correcto, pero en lugar de un backtracking puede resolverse mediante Dijkstra, cuya complejidad para un grafo G = (V, E) es O((V + E)logV) mientras que el backtracking no es polinómico.

He picado Dijkstra  en C++ para el problema, he probado un par de ejemplos y los resuelve bien. El código es simple así que no debería ser problema pasarlo a otro lenguaje sabiendo un poco de C++.

Código (cpp) [Seleccionar] Expandir

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

const int INF = 1000000000;
const int arr1[] = {1, -1, 0, 0};
const int arr2[] = {0, 0, 1, -1};

typedef pair<int, int> PII;
typedef pair<int, PII> PIPII;

void dijkstra(int fini, int cini, int ffin, int cfin, vector<vector<int> >& M) {
    int n = M.size(), m = M[0].size();
    vector<vector<int> > d(n, vector<int>(m, INF));
    d[fini][cini] = 0;
    priority_queue<PIPII> Q;
    Q.push(PIPII(0, PII(fini, cini)));
    while (not Q.empty()) {
        int f = Q.top().second.first, c = Q.top().second.second, dist = -Q.top().first;
        Q.pop();
        if (dist != d[f][c]) continue;
        for (int i = 0; i < 4; ++i) {
            int nf = f + arr1[i], nc = c + arr2[i];
            if (nc < 0 or nc >= m or nf < 0 or nf >= n or M[nf][nc] == 0) continue;
            if (d[nf][nc] > d[f][c] + M[nf][nc]) {
                d[nf][nc] = d[f][c] + M[nf][nc];
                Q.push(PIPII(-d[nf][nc], PII(nf, nc)));
            }
        }
    }
    if (d[ffin][cfin] == INF) cout << "No existe camino" << endl;
    else cout << "Minima distancia: " << d[ffin][cfin] << endl;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > M(n, vector<int> (m));
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> M[i][j];
    int fini, ffin, cini, cfin;
    cin >> fini >> ffin >> cini >> cfin;
    if (M[fini][cini] == 0) cout << "Muro en posicion inicial" << endl;
    else dijkstra(fini, cini, ffin, cfin, M);
}

Es bastante simple, para cada numero mira si los siguientes son menores, en el caso de que lo sean, llama a la función que los cambia, es una manera eficiente de ordenar una lista. Por ahí te han dejado un link a la wikipedia que lo explica bastante bien.

No es una forma nada eficiente de ordenar el algoritmo de ordenación por selección. Lo que sucede es que es muy simple y por eso es de los primeros algoritmos que se enseñan. Este algoritmo tiene un coste de O(n²), mientras que otros algoritmos de ordenación como heap sort, merge sort o quicksort tienen costes O(nlogn) (quicksort en caso peor es cuadrático, pero en caso medio tiene esa complejidad). De los algoritmos cuadráticos típicos (selection sort, bubble sort e insertion sort), el único que sirve es insertion sort, porque aunque sea cuadrático en caso peor, generalmente es algo mejor y para entradas pequeñas es más rápido que los que he dicho antes.