Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
4 / 2 / 2
Регистрация: 22.11.2019
Сообщений: 86

Алгоритм Вагнера-Фишера

22.04.2023, 17:22. Показов 675. Ответов 6
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Нужно реализовать алгоритм Вагнера-Фишера. По заданию необходимо сделать класс, есть некоторые наброски
Проблемы возникают в методе Init(), использовать двумерный массив нельзя по заданию, матрицу представлять, как указатель на массив целых.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#pragma once
#include <iostream> 
#include <string>
#include <exception>
 
using namespace std; 
 
class WF {
private:
    int* pm; 
    int n;
    int m;
    string s; 
    string t;
 
public:
    WF() 
    {
        pm = nullptr;
        m = 0; 
        n = 0; 
    }
 
    ~WF()
    {
        if (pm != nullptr)
        {
            delete[] pm;
        }
    }
 
    void Clear() // решение проблемы повторной инициализации, вызываем перед методом Init(); 
    {                  // освобождение памяти для указателя pm, обнуление размерности матрицы 
        if (pm != nullptr)
        {
            delete[] pm;
        }
        pm = nullptr;
        m = 0; 
        n = 0;
    }
 
    void Init(const char* sc, const char* tc) 
    {
        s = string(sc);
        t = string(tc);
        if (pm != nullptr) {
            delete[] pm;
        }
        m = s.length() + 1;
        n = t.length() + 1;
        pm = new int[n * m];
        for (int i = 0; i <= n; ++i) 
        {
            pm[i, 0] = i;
        }
        for (int j = 0; j <= m; ++j)
        {
            pm[0, j] = j; 
        }
        for (int j = 1; j <= m; ++j)
        {
            for (int i = 1; i <= n; ++i)
            {
                if (s[i - 1] == t[j - 1])
                {
                    pm[i, j] = pm[i - 1, j - 1];
                }
                else
                {
                    pm[i, j] = min({ pm[i - 1, j], pm[i, j - 1], pm[i - 1, j - 1] }) + 1;
                }
            }
        }
    }
 
    int Rows() const
    {
        return m; 
    }
 
    int Columns() const
    {
        return n; 
    }
 
    int Get(int i, int j) const
    {
        if (i >= 0 && j >= 0 && i < m && j < n) 
        {
            return pm[i * j];
        }
        else
        {
            throw out_of_range("Index is out of range!");
        }
    }
 
    void Set(int i, int j, int value)
    {
        if (i >= 0 && j >= 0 && i < m && j < n)
        {
            pm[i * j] = value;
        }
        else
        {
            throw out_of_range("Index is out of range!");
        }
    }
 
    int Distance() const
    {
        return pm[n, m];
    }
 
    void PrintMatrix()
    {
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cout << pm[i * j] << " ";
            }
            cout << endl; 
        }
    }
};
и блок main
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include "WF.h"
 
using namespace std; 
 
int main()
{
    WF object;
    object.Clear();
    object.Init("nature", "nat"); 
    object.PrintMatrix(); 
    return 0; 
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.04.2023, 17:22
Ответы с готовыми решениями:

Алгоритм Фишера-Йетса
Может кто-то объяснить, зачем в 12 строчке мы отнимаем 1 от N, а в 14 строчке пишем (i + 1)? спасибо. #include &lt;stdio.h&gt; ...

Алгоритм Штёр-Вагнера для поиска рёбер, входящих в минимальный разрез
Дана задача в которой необходимо вывести список рёбер взвешенного неориентированного графа, входящих в минимальный разрез. Проблема в том,...

Алгоритм Вагнера - Фишера
for (int i = 1; i &lt;= n; ++i) { for (int j = 1; j &lt;= m; ++j) { if (s == t) { dp = dp; } else { dp = min(dp,...

6
Лежебока
 Аватар для Donkix
328 / 244 / 95
Регистрация: 12.05.2021
Сообщений: 1,429
Записей в блоге: 2
22.04.2023, 17:29
Цитата Сообщение от Firefox6783 Посмотреть сообщение
pm[i, 0]
такое не прокатит, нужно что-то типа такого
C++
1
2
3
for( int i = 0; i < n;i++)
    for( int j = 0; j < n;i++)
        pm[i*n+j*m] = i;
0
4 / 2 / 2
Регистрация: 22.11.2019
Сообщений: 86
22.04.2023, 17:33  [ТС]
Donkix, то есть в программе такого типа использовать запись элемента массива через pm[i * j]?
0
Лежебока
 Аватар для Donkix
328 / 244 / 95
Регистрация: 12.05.2021
Сообщений: 1,429
Записей в блоге: 2
22.04.2023, 17:35
Цитата Сообщение от Firefox6783 Посмотреть сообщение
i <= n;
Так не делай, иначе обеспечишь выход за границу
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
22.04.2023, 17:36
Цитата Сообщение от Firefox6783 Посмотреть сообщение
запись элемента массива через pm[i * j]?
Нет, "одномерный" индекс элемента, находящегося в i-ой строке и j-ом столбце вычисляется как i * <число столбцов> + j.
0
Лежебока
 Аватар для Donkix
328 / 244 / 95
Регистрация: 12.05.2021
Сообщений: 1,429
Записей в блоге: 2
22.04.2023, 17:39
Firefox6783, как сказали чуть ранее, обьект пространства(i,j,k,...) нужно умножить на его размер(n,m,...) и сложить с обьектом другого пространства
0
4 / 2 / 2
Регистрация: 22.11.2019
Сообщений: 86
22.04.2023, 18:49  [ТС]
Donkix, всем спасибо, получилось
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.04.2023, 18:49
Помогаю со студенческими работами здесь

Недостатки расстояния Левенштейна, алгоритм Вагнера-Фишера
Известно, что расстояние Левенштейна обладает следующим недостатком: расстояние между совершенно разными короткими словами оказываются...

Анализ ошибок в тексте, алгоритм Вагнера
Добрый день. Помогите пожалуйста с задачей. Надо реализовать на прологе алгоритм Вапгнера(Исправление ошибок в тексте) Заранее всех...

Алгоритм Фишера - Йейтса
необходимо реализовать алгоритм тасовки Фишера - Йейтса, который будет тасовать вводимый пользователем текст и выводить все тасовки которые...

Алгоритм тасования Фишера-Йетса
Здравствуйте Уважаемые Программисты киберфорума... В паутине поискал и не нашел что нужно... Я новичок пишу учусь так сказать... Дайте...

Сгенерировать беспорядок чисел 1..n без повторений, используя "современный" алгоритм Фишера-Йетса
Ни как не пойму как это решить Беспорядок 1..n Сгенерировать беспорядок чисел 1..n без повторений, используя &quot;современный&quot;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru