Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)
-   -   Алгоритм Беллмана-Форда (https://forum.antichat.xyz/showthread.php?t=154865)

winflip 08.11.2009 13:38
Алгоритм Беллмана-Форда
 
Добрый день. Может быть не в тот раздел пишу, но ладно. В общем скажите, где можно найти исходник на c++ реализации алгоритма Беллмана-Форда(без использования классов). Или, если, кто знает этот алгоритм, просто его опишите, а то я c algolist.manual.ru и википедии ничё не понял. Заранее благодарю

Forcer 08.11.2009 16:41
http://snippets.dzone.com/posts/show/4828

Noir 09.11.2009 11:14
Алгоритм начинает свою работу в точке, к которой следует проложить маршрут(называется исходной точкой). Расстояние от этой точки до самой себя задается равным нулю, а растояние до всех остальных точек считается равным бесконечности.
Основное предположение, выдвигаемое в данном алгоритме, заключается в том, что от
любой точки системы существует как минимум один маршрут к исходной точке. Ни одна
точка не является полностью изолированной. Кроме тoгo, по достижении исходной точки маршрут заканчивается. Он не может пройти через исходную точку, а затем вернyться назад, образовав петлю. Таким образом, нельзя пройти ПО одному и тому же пути дважды.
На каждой итерации на схему наносится путь от каждой удалённой точки до исходной точке, причём колличество переходов на этом пути соответствует номеру итерации. Рядом с каждым переходом записывается его длина.

winflip 09.11.2009 17:22
Если не сложно, скажите ещё одну весчь)) Я написал исходник на основе алгоритма, который дан на википедии, называется тест простоты милера-рабина(или миллера-рабина), так вот исходник:
Код:
#include <iostream>
#include <cmath>
int is_prime(int m){
        using namespace std;
        int r = 1000;
        int t = m-1;
        int s = 0;
        bool b = true;
        if(m%2==0){
                return false;
        }
        if(m==1){
                return false;
        }
        if(m==2){
                return true;
        }
        while(t%2==0 || b){
                b = false;
                s++;
                t=t/2;
        }
        for(int i=1;i<r+1;i++){
                int a = 2+rand()%(m-2);
                int x = int(float(pow(float(a),float(t))))%m;
                if((x==1)||(x==m-1)){
                        continue;
                }
                for(int j=1;j<s;j++){
                        x=int(float(pow(float(x),2)))%m;
                        if(x==1){
                                return false;
                        }
                        if(x==m-1){
                                continue;
                        }
                }
        }
        return true;
}
int main(){
        using namespace std;
        int a,b;
        cin >> a >> b;
        for(int i=a;i<b;i++){
                if(is_prime(i)){
                        cout << i << " ";
                }
        }
        cin >> a;
        return 0;
}
Проблема в том, что он неработает, смущает концовка, потому что в алгоритме я её не понял.))) Помогите. Простой тест a=3,b=20. Он выводит 15(хотя оно составное), и не выводит 17(оно то как раз простое)


Время: 14:47