Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.72/18: Рейтинг темы: голосов - 18, средняя оценка - 4.72
ManHunter
13 / 13 / 6
Регистрация: 16.05.2011
Сообщений: 152
Записей в блоге: 2
1

Процент схожести строк

01.04.2012, 23:21. Просмотров 3224. Ответов 8
Метки нет (Все метки)

Всем здрасте. Вообщем дали мне по лабораторным ОСиСП такое задание:
1) Выполнить индивидуальное задание последовательным алгоритмом;
2) Выполнить индивидуальное задание параллельным алгоритмом (обязательно использовать для разграничения общих ресурсов системные объекты синхронизации);
3) Сделать анализ быстродействия последовательного и параллельного алгоритмов.

УСЛОВИЕ ЗАДАНИЯ:
Сравнение строк произвольного содержания и вывод процента схожести.

Я не уверен в алгоритме который я придумал для решения задачи.
Допустим делаем так:
I. Вводим с клавиатуры две строки;
II. По-символьно (каждый символ) проверяем на схожесть и считаем совпадения X;
III. Проверяем длинну строки strlen(S1) - длинна первой строки strlen(S2) - второй, и считаем среднее, т.к. длинны могут быть разными N = strlen(S1)/strlen(S2). Затем делим кол-во совпадений на длину строки X/N * 100;

Это не главный вопрос который я хотел спросить, скорее даже просто хоте попросить совета.
Главный вопрос - это как сделать "параллельный алгоритм", у меня сейчас пошла тема "Потоки" или по другому "Нити".
Допустим с теорией создания потока я знаком, но я не знаю принцип как он будет выполнять параллельно все эти проверки. Возможно нужно поменять алгоритм описанный выше?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2012, 23:21
Ответы с готовыми решениями:

Вычислить процент положительных чисел, процент отрицательных чисел и процент нулей
1.Загадать случайно 100 целых чисел в диапазоне от -100 до 100. Вычислить...

Вычислить процент положительных чисел, процент отрицательных чисел и процент нулей
В цикле с клавиатуры вводятся 10 целых чисел. Вычислить процент положительных...

Написать программу, которая предлагает пользователю ввести 10 чисел, вычисляет процент положительных и отрицательных чисел и процент нулей и выводи
помогите =) написать программу, которая предлагает пользователю ввести 10...

Отсортированный хэш-вектор бинарной схожести для быстрого поиска
Есть набор 64-х разрядных чисел, их может быть примерно 20 000 ... 40 000....

определить процент
Известно количество жителей в городе. Сведения о мужчинах и женщинах поместили...

8
Avazart
Эксперт С++
7722 / 5631 / 549
Регистрация: 10.12.2010
Сообщений: 25,401
Записей в блоге: 17
02.04.2012, 00:31 2
Возможно вы неправильно поняли оценку схожести?
Например строка "12345" и строка "23456" схожи?
Предположу что некоторая схожесть есть, но ваш алгоритм, как я полагаю, скажет что схожести нет...
Является ли положение символов важным в понятии схожести?
0
ManHunter
13 / 13 / 6
Регистрация: 16.05.2011
Сообщений: 152
Записей в блоге: 2
02.04.2012, 20:19  [ТС] 3
Цитата Сообщение от Avazart Посмотреть сообщение
Возможно вы неправильно поняли оценку схожести?
Например строка "12345" и строка "23456" схожи?
Предположу что некоторая схожесть есть, но ваш алгоритм, как я полагаю, скажет что схожести нет...
Является ли положение символов важным в понятии схожести?
да, мой алгоритм не покажет схожести. Я думаю, что всё таки нужно делать как описывал выше.
Вообщем написал я программу, а теперь осталось создать копию программы только с использованием потоков pthread.h
Буду пробовать написать, если есть предложения как это можно реализовать, я бы с удовольствием выслушал.
0
Avazart
Эксперт С++
7722 / 5631 / 549
Регистрация: 10.12.2010
Сообщений: 25,401
Записей в блоге: 17
02.04.2012, 20:34 4
Ваш алгоритм слишком прост поэтому нет смысла его раскидывать( да и нечего раскидывать) по потокам.
0
ManHunter
13 / 13 / 6
Регистрация: 16.05.2011
Сообщений: 152
Записей в блоге: 2
02.04.2012, 21:18  [ТС] 5
Цитата Сообщение от Avazart Посмотреть сообщение
Ваш алгоритм слишком прост поэтому нет смысла его раскидывать( да и нечего раскидывать) по потокам.
я тоже об этом думал и поэтому добавил третью строку и ищу в каждой строке процент схожести - S1 и S2, S1 и S3, S2 и S3.
Для этого я вызываю функцию process в трёх потоках.
Вот столкнулся с проблемой. На примере было указано в функции только один входящий параметр, а у меня их 2 - void *process(char *S1, char *S2), как тогда правильно создать поток?

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
 
void *process(char *S1, char *S2)
{
    int i, x=0;
    double K, N;
    if(strlen(S1)>=strlen(S2))
    {
        for(i=0; i != strlen(S2); i++){
            if(S1[i] == S2[i])
                x++;
                sleep(1);
        }
    }
    else
        for(i=0; i != strlen(S1); i++){
            if(S1[i] == S2[i])
                x++;
                sleep(1);
        }
    N = (strlen(S1)+strlen(S2))/2;
    printf("%.0f",((x/N)*100));
}
 
void main(void)
{
    pthread_t t1, t2, t3;
    char S1[20], S2[20], S3[20];
    printf("Enter S1, S2, S3\n");
    gets(S1);
    gets(S2);
    gets(S3);
    printf("%s \n%s \n%s \n", S1, S2, S3);
    pthread_create(&t1, NULL, process, (char *, char *)S1, S2);
    pthread_create(&t2, NULL, process, (char *, char *)S1, S3);
    pthread_create(&t3, NULL, process, (char *, char *)S2, S3);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_join(t3, NULL);
    printf(" - процент совпадения строк S1 и S2 \n");
    printf(" - процент совпадения строк S1 и S3 \n");
    printf(" - процент совпадения строк S2 и S3 \n");
}
0
Arkadiy_Ukupnik
0 / 0 / 0
Регистрация: 16.04.2013
Сообщений: 11
16.04.2013, 12:25 6
У меня точь в точь такое же задание. Не могли бы вы поделится кодом, если у вас остался?)
0
gazlan
3141 / 1917 / 311
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
16.04.2013, 13:08 7
Levenshtein distance
0
ManHunter
13 / 13 / 6
Регистрация: 16.05.2011
Сообщений: 152
Записей в блоге: 2
16.04.2013, 13:54  [ТС] 8
Arkadiy_Ukupnik,
Вроде нашел исходник, только не помню какие именно там файлы. Вообщем по коду можешь посмотреть.
Сразу хочу сказать, что там может быть не доработанная программа.
https://drive.google.com/folderview?...W8&usp=sharing
1
Arkadiy_Ukupnik
0 / 0 / 0
Регистрация: 16.04.2013
Сообщений: 11
17.04.2013, 23:03 9
Премного благодарен.
0
17.04.2013, 23:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.04.2013, 23:03

Вычитаем процент от числа.
Вот фрагмент программки... weight = growth - 110; ideal_weight = weight -...

Найти процент P от суммы S
Написать программу, которая находит процент P от суммы S. честно очень стыдно...

Процент гласных в предложении
В программе нужно ввести предложение окончание предложения точка. После этого...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru