Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
pasha5442893
0 / 0 / 0
Регистрация: 19.12.2011
Сообщений: 3
#1

интересная задача по сорту! :) - C++

21.12.2011, 17:35. Просмотров 228. Ответов 0
Метки нет (Все метки)

люди пожалусто помогите последняя задача по лабе...старый долг!

Условие!:
Имеется массив из n чисел от 0 до (2 в степени k) -
1, каждое из которых мы будем рассматривать как k-битовое слово.
Используя проверки "i-ый бит равен 0" и "i-ый бит равен 1" вмес-
то сравнений, отсортировать все числа за время порядка n
Решение. Отсортируем числа по последнему биту (см. предыду-
щую задачу), затем по предпоследнему и так далее. В результате
они будут отсортированы. В самом деле, индукцией по i легко до-
казать, что после i шагов любые два числа, отличающиеся только в
i последних битах, идут в правильном порядке. (Вариант: после i
шагов i-битовые концы чисел идут в правильном порядке.)

Аналогичный алгоритм может быть применен для m-ичной систе-
мы счисления вместо двоичной.

Помогите отсортить Двоичные числа ПЛИЗ

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
#include <iostream>  // сортирует сначала числа потом переводит в двоичную, а надо отсортить ДВОИЧНЫЕ!
#include <list>
 
using namespace std;
 
struct Node{
    int deg [64];
    //int k;
    Node (){ for (int i = 0; i<64; i++) deg [i]=0;};
};
 
int main (){
    Node a [100];
    int n;
    cout<<"Vvedite kolichestvo chisel"<<endl;
    cin >> n;
    for (int i = 0; i< n; i++){
        int p;
        cin >> p;
        int j=0;
        while (p){
            a [i].deg [j]=p%2;
            p/=2;
            j++;
        }
//      a [i].k = j-1;
 
 
    }
    list <Node> l0,l1;
    l0.clear ();
    l1.clear ();
    for (int i=0; i<63; i++){
        for (int j = 0; j<n; j++){
            if (a [j].deg [i]) l1.push_back (a [j]); else l0.push_back (a[j]);
        }
        int j = 0;
        while (!l0.empty ()) {
            a[j]=l0.front ();
            l0.pop_front ();
            j++;
        }
        while (!l1.empty ()) {
            a[j]=l1.front ();
            l1.pop_front ();
            j++;
        }
    }
    for (int i = 0; i<n; i++){
        for (int j = 0           ; j<64; j++) cout << a [i].deg [j];
        cout << endl;
        
    }
    system ("pause");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2011, 17:35     интересная задача по сорту! :)
Посмотрите здесь:
Интересная задача на графы C++
C++ Интересная задача на вывод процентов
C++ Очень интересная задача, не все смогут
Судоку. Задача довольно-таки интересная C++
C++ Интересная задача. (вывод своего кода на экран)
C++ интересная головоломка
C++ Интересная головоломка
C++ Интересная конструкция в C++
Интересная штука C++
C++ Интересная задачка
Интересная сортировка C++
Интересная сортировка C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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