Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
4 / 4 / 3
Регистрация: 24.07.2015
Сообщений: 75
1

Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием

14.02.2016, 23:19. Показов 1031. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Ножно подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием.
Числа в файле расположены каждое в новой строке.

Помогите найти ошибку.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef long long LL;
 
LL interpolate(int x[], int start, int middle, int a) {
    int end = a;
    int i, j, k, *b;
    LL c;
    (int *) b = (int*) malloc ((end+1)*sizeof(int));
    for(i = start; i <= middle; i++) b[i] = x[i];
    for(j = end; i <= end; i++, j--) b[i] = x[j];
 
    for(c = 0, j = end, i = k = start; k <= end; k++)
        if(b[i] <= b[j])
            x[k] = b[i++];
        else {
          x[k] = b[j--];
          c = c + (middle - i + 1);
        }
        free(b);
    return c;
}
 
LL merge_sort(int x[], int start, int end) {
    int middle;
 
    if(start >= end) return 0;
    middle = (start + end) / 2;
 
    return  merge_sort(x, start, middle) +
            merge_sort(x, middle+1, end) +
            interpolate(x, start, middle, end);
}
 
int main() {
    int arr[100000], i=0;
    FILE * f;
    f = fopen("3.txt", "r");
    if (f == 0)
        {
            printf ("Error");
            _getch();
            return 0;
    }
    while (fscanf(f,"%d\n", &arr[i])!=EOF) i++;
    printf("Number of inversions are %lld \n", merge_sort(arr, 0, 100000-1));
    _getch();
    return 0;
}
Вложения
Тип файла: txt 3.txt (2.8 Кб, 1 просмотров)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.02.2016, 23:19
Ответы с готовыми решениями:

Подсчитать количество инверсий в массиве
Нужно написать программу, которая подсчитывает колличество инверсий в массиве со временем работы в...

Алгоритм сортировки слиянием
Ребятки помоги! Понять что здесь не так: public static IEnumerable&lt;T&gt; MSort&lt;T&gt;(this...

Алгоритм сортировки слиянием на CUDA
Здравствуйте, начал изучать cuda попытался реализовать один из алгоритмов сортировки но вроде бы...

Ассемблерные вставки в C++. Алгоритм сортировки слиянием
Нужна помощь.Необходимо реализовать алгоритм сортировки слиянием по возрастанию из элементов...

1
4 / 4 / 3
Регистрация: 24.07.2015
Сообщений: 75
16.02.2016, 22:44  [ТС] 2
Если кому-то интересно, вот уже решил (функция int), добавил подсчет чисел.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    int i, size=0;
    FILE *pfile=fopen("D:\\IntegerArray.txt","r"); 
    setlocale(LC_ALL, "ukr");
    while(!feof(pfile) && !ferror(pfile))
    {
         fscanf(pfile, "%*[^\n]%*c");
         size++;
    }
    rewind(pfile);
    int *A = (int*) malloc(size*sizeof(int));  
      
    for(i = 0; i < size; i++) fscanf(pfile, "%d\n", &A[i]);
    fclose(pfile);
 
    printf("Number of inversions are %lld \n", merge_sort(A, 0, size-1));
    free(A);
    _getch();
    return 0;
}
0
16.02.2016, 22:44
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.02.2016, 22:44
Помогаю со студенческими работами здесь

алгоритм внешней сортировки простым слиянием
Дан файл содержащий следующие сведения о пассажирах поезда:фамилия масса багажа.упорядочить...

Необходимо подсчитать количество инверсий
Имеются последовательности: Необходимо подсчитать количество инверсий. Подскажите, пожалуйста,...

Алгоритм сортировки слиянием. Исправить ошибки в коде
#include &lt;iostream&gt; #include &lt;time.h&gt; void merge(int array, int left, int right, int n) {...

Реализуйте алгоритм сортировки слиянием применительно к односвязным спискам
Реализуйте алгоритм сортировки слиянием применительно к односвязным спискам. Основные шаги...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru