Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
Artem_007
1 / 1 / 0
Регистрация: 23.10.2012
Сообщений: 30
1

Алгоритм Госпера и подсчет завершающих нулевых битов

25.11.2013, 23:31. Просмотров 1319. Ответов 7
Метки нет (Все метки)

Есть три вопроса:
1.Реализовать алгоритм Госпера. Множество – одномерный статический массив целых чисел из 32 элементов. Подмножества – целые 32-хразрядные числа.
2. Подсчет завершающих нулевых битов в 32-хразрядном числе.
3. Реализовать алгоритм поиска пути в лабиринте. Волновой алгоритм. Представление графа – матрица смежности. (тут я еще примерно представляю как работает, но не пойму, как вообще задается этот лабиринт, без последнего условия я бы представил его в виде простого двумерного массива с 3 состояниями: 1 -- нельзя пройти, 2 -- можно пройти, 3 -- уже прошли и там бы как-то скоординировался, а вот с графами у меня яма в моих знаниях, могли бы подсказать чисто теоритическую реализацию?)
Что это и как этим пользоваться? Хотелось бы литературу найти, даже книжек вразумительных не нашел по первым двум вопросам. Пока что понятия не имею что это вообще, спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2013, 23:31
Ответы с готовыми решениями:

Алгоритм удаления из массива нулевых элементов
Задан массив действительных чисел. Записать алгоритм удаления из массива...

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

Подсчет ведущих нулевых битов в 32-хразрядном числе
Как я понял ведущие 0 биты в числе это первые 0,но нет двоичных чисел с 0...

Количество нулевых битов
in1 4бита in2 4бита out1 1бит out2 1бит out3 1бит На входе...

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

7
gazlan
3161 / 1920 / 312
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
26.11.2013, 04:05 2
Грэхем Р., Кнут Д., Паташник О. — Конкретная математика
Генри С. (мл.) Уоррен Алгоритмические трюки для программистов

Нестеренко А. Ю. Алгоритмы поиска длин циклов в последовательностях и их приложения
Путь в двумерном лабиринте - волновой алгоритм
2
Artem_007
1 / 1 / 0
Регистрация: 23.10.2012
Сообщений: 30
26.11.2013, 13:56  [ТС] 3
Цитата Сообщение от gazlan Посмотреть сообщение
Грэхем Р., Кнут Д., Паташник О. — Конкретная математика
Генри С. (мл.) Уоррен Алгоритмические трюки для программистов

Нестеренко А. Ю. Алгоритмы поиска длин циклов в последовательностях и их приложения
Путь в двумерном лабиринте - волновой алгоритм
Это я пролистывал все, с лабиринтами вроде разобрался, но так и не нашел определения "нулевого завершающего бита", что это вообще? В книжках все написано:
Все представлено в виде двоичных чисел, бла-бла, вот функция нахождения "количества нулевых завершающих битов", и сразу дальше, ни пояснений, что это за зверь, ничего вразумительного, хотелось самый простенький пример что куда и зачем, в лабе 32-ух разрядные числа, мне нужно понимать смысл алгоритма) Заранее спасибо )
0
gazlan
3161 / 1920 / 312
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
26.11.2013, 16:16 4
Цитата Сообщение от Artem_007 Посмотреть сообщение
"нулевого завершающего бита
Я это понимаю так:

По заданию, слова состоят из 32 бит. Нумеруете их, например, слева направо. Самый правый (завершающий) бит может быть либо 0, либо 1. Если он 0, определить число предшествующих ему нулей.
1
Artem_007
1 / 1 / 0
Регистрация: 23.10.2012
Сообщений: 30
27.11.2013, 15:36  [ТС] 5
Цитата Сообщение от gazlan Посмотреть сообщение
Я это понимаю так:

По заданию, слова состоят из 32 бит. Нумеруете их, например, слева направо. Самый правый (завершающий) бит может быть либо 0, либо 1. Если он 0, определить число предшествующих ему нулей.
Мм..Т.е. все так просто?
например число 0101101010101011010101011001000, то количество завершающих битов будет равно 3?
а если 0101101010101011010101011001001, то количество равно нулю?
Я думал что-то мудреное, спасибо )

Добавлено через 21 час 41 минуту
Цитата Сообщение от Artem_007 Посмотреть сообщение
Мм..Т.е. все так просто?
например число 0101101010101011010101011001000, то количество завершающих битов будет равно 3?
а если 0101101010101011010101011001001, то количество равно нулю?
Я думал что-то мудреное, спасибо )
Есть вопрос, не особо понимаю, как работает данная функция:
Java
1
2
3
4
5
6
7
8
9
10
public static int countBits(int x) {
        int n;
        if (x == 0) return (32);
        n = 1;
        if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >> 16;} 
        if ((x & 0x000000FF) == 0) {n = n +8; x = x >> 8;}
        if ((x & 0x0000000F) == 0) {n = n +4; x = x >> 4;}
        if ((x & 0x00000003) == 0) {n = n +2; x = x >> 2;}
        return n - (x & 1);
    }
Может кто в кратце объяснить?
Что это за числа "0x0000FFFF" ?) Если я правильно понял, то это в шестнадцатиричной с.с., но что происходит в самом условии?) Читал книжки, но понять так и не смог)
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
27.11.2013, 15:52 6
Цитата Сообщение от Artem_007 Посмотреть сообщение
но что происходит в самом условии?)
Сравнение с нулём последних бит числа...

Цитата Сообщение от Artem_007 Посмотреть сообщение
Может кто в кратце объяснить?
Если они вдруг нули, то увеличивается счётчик нулей, а число сдвигается так, чтобы их не посчитать ещё раз, но посчитать предшествующие им нули.

Хитрый алгоритм. Надо подумать над тройкой и последней проверкой x на чётность, остальное вроде вполне логично.

Добавлено через 46 секунд
Цитата Сообщение от Artem_007 Посмотреть сообщение
Что это за числа "0x0000FFFF" ?)
Ну переведи калькулятором в двоичную систему и посмотри
1
gazlan
3161 / 1920 / 312
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
27.11.2013, 17:43 7
Цитата Сообщение от Artem_007 Посмотреть сообщение
Что это за числа "0x0000FFFF"
Битовая маска для младшей половины двойного слова (16 бит). Также как у окулиста, например, просят закрыть один глаз, x & 0x0000FFFF закрывает (обнуляет) половину двойного слова. Соответственно, 0x000000FF выделяет младшую половину одинарного слова - младший байт (8 бит), а 0x0000000F - младшую половину байта (ниббл).

Добавлено через 5 минут
Цитата Сообщение от Qwertiy Посмотреть сообщение
Надо подумать над тройкой и последней проверкой x на чётность
Это, соответственно, половина и четверть (половина от половины) ниббла. То есть, размер маски, последовательно (фрактально) сокращается вдвое: 16-8-4-2-1.
1
Artem_007
1 / 1 / 0
Регистрация: 23.10.2012
Сообщений: 30
04.12.2013, 16:09  [ТС] 8
Цитата Сообщение от gazlan Посмотреть сообщение
Битовая маска для младшей половины двойного слова (16 бит). Также как у окулиста, например, просят закрыть один глаз, x & 0x0000FFFF закрывает (обнуляет) половину двойного слова. Соответственно, 0x000000FF выделяет младшую половину одинарного слова - младший байт (8 бит), а 0x0000000F - младшую половину байта (ниббл).

Добавлено через 5 минут


Это, соответственно, половина и четверть (половина от половины) ниббла. То есть, размер маски, последовательно (фрактально) сокращается вдвое: 16-8-4-2-1.
Теперь опять этот алгоритм Госпера:
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
// AOIS_lab04.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <conio.h>
#include <math.h>
#define __max(a,b)  (((a) > (b)) ? (a) : (b))
 
using namespace std;
 
int nlz(unsigned x) {
    int y, n;
    n = 0;
    y = x;
L:  if(x < 0) return n;
    if (y == 0) return 32 - n;
    n = n + 1;
    x = x << 1;
    y = y >> 1;
    goto L;
}
 
int ntz(unsigned x) {
    int n;
    x = ~x & (x - 1);
    n = 0;
    while(x != 0) {
        n = n + 1;
        x = x >> 1;
    }
    return n;
 
}
 
void ld_Gosper (int (*f) (int), int X0, int *mu_l, int *mu_u, int *lambda)
{
    int Xn, k, m, kmax = 0, n, lgl;
    int T[33];
    T[0] = X0;
    Xn = X0;
    for(n = 1; ; n++)
    {
        Xn = f(Xn);
        kmax = 31 - nlz(n);
        for(k = 0; k <= kmax; k++)
        {
            if(Xn == T[k]) goto L;
        }
        T[ntz(n + 1)] = Xn;
    }
L:
    m = ((((n >> k) - 1) | 1) << k) - 1;
    *lambda = n - m;
    lgl = 31 - nlz(*lambda - 1);
    *mu_u = m;
    *mu_l = m - __max(1, 1 << lgl) + 1;
}
 
int f (int x) {
    if (x < 1)
        return 1000;
    if (x == 1000)
        return 1;
    else if (x < 10)
        return ++x;
    else
        return ++x - 10;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int a = 1000,
        b = 0,
        c = 0,
        d = 0;
    for (int i = 0; i < 35; i++)
        cout << f(i) << " ";
    cout << endl;
    ld_Gosper(f, a, &b, &c, &d);
    cout << a << " X0 \n"<< b <<" mu_l \n"<< c <<" mu_u \n" << d << " lambda \n"<<endl;
    _getch();
    return 0;
}
Вроде все списано с книжки, функции nlz и ntz работают более-менее корректно, на сколько я понял, функцию примерную набросал, последовательность есть, но не ищет, в массиве Т хранится какая-то ересь, которая под описание из книжки не подходит, как мне кажется:
вот тут страница нужная
Может функция неправильно определена? Или как вообще быть?)
0
04.12.2013, 16:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2013, 16:09

Подсчет битов
На входе даны 2 последовательности по 8 бит IN_0, IN_1. OUT_0 изначально...

Подсчет суммы битов в байте
Помогите пожалуйста!) Написать функцию подсчета суммы битов в байте. ...

Подпрограмма (для Intel 80x86) определяющая количество нулевых двоичных разрядов (битов)
Помогите пожалуйста написать программу. Нужно написать подпрограмму (для Intel...


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

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

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