Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

21.12.2011, 17:35. Просмотров 237. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2011, 17:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос интересная задача по сорту! :) (C++):

Интересная задача на графы - C++
Помогите решить. Никак не могу придумать способ. Мне говорят, что на графы, а связать это с графами не могу. Может хоть способ решения и...

Интересная задача на вывод процентов - C++
Задан текст, слова которого разделены %. Выяснить и вывести на экран, какой процент слов в тексте начинается на заданную букву (буква...

Судоку. Задача довольно-таки интересная - C++
Написать программу через рекурсию, делающую судоку.... Добавлено через 2 часа 50 минут а вроде задание так звучит: дан текстовый...

Очень интересная задача, не все смогут - C++
Напишите программу, использующую рекурсию, определяющую положение восьми ферзей на шахматной доске, при котором ни один ферзь не угрожает...

Интересная задача. (вывод своего кода на экран) - C++
Вот, сидели с другом на паре и возник вопрос: Можно ли в с\с++ написать программу , которая выведет сама свой код на экран? В голову...

Интересная задача - C++
Добрый вечер! если не трудно можете мне помочь с решение задания Шарик бросают в интересное устройство, схематично представлен на...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2011, 17:35
Привет! Вот еще темы с ответами:

Интересная задача на предельные значения переменных - C++
Проинициализируйте переменнyю i таким образом, чтобы распечаталось слово. int i=???; int j = -i; if (i &gt;= 0) ...

Интересная задача с географическими координатами и идеальным поездом передвигающимся от силы гравитации - C++
Всем доброго времени суток. С дублировал тему так как на форуме явы народа почти нет. Да и по больше части меня интересуют формулы и...

Интересная головоломка - C++
1.С помощью текстового редактора создать файл который содержит текст.Длина ряда с текстом не должна превышать 80 символов.Это входной файл....

Интересная задачка - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; int main() { double z1,z2; double a,b,c,d,s,t,u; ...


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

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

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