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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
Задрот С
0 / 0 / 0
Регистрация: 19.09.2009
Сообщений: 57
#1

Номер двоичного разряда - C++

13.03.2010, 14:43. Просмотров 1615. Ответов 14
Метки нет (Все метки)

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

Для длинного целого числа N определить, если возможно, номер двоичного разряда, для которого выполняется условие: число единичных разрядов справа от него равно числу единичных разрядов слева от него.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2010, 14:43     Номер двоичного разряда
Посмотрите здесь:

Сумма младшего и старшего разряда - C++
Напишите программу, считающую сумму старшего и младшего разряда заданного с клавиатуры целого числа. C++

Вопрос из разряда страшно спросить - C++
Вот есть кусок кода. sp<MetaData> MediaBuffer::meta_data() { return mMetaData; } Мне не понятно что означает вот эти <....>?...

Вывести цифры младшего и старшего разряда - C++
Условие: Написать программу. Дано n-значное число longint. Провести с ним действия согласно номеру варианта ( 17 ). Вывести только...

Округление до разряда где сходится результат - C++
Привет всем! Есть такая вот проблема. При вычислении одного и того же числа двумя способами, имеем некоторые значения, например 0.385 и...

Сдвинуть элементы массива на два разряда вправо - C++
Даны массивы A , B . Получить новые массивы путем сдвига элементов в массивах на два разряда вправо, освободившиеся слева элементы...

Нужно сдвинуть число на 4 разряда влево и вправо - C++
Нужно сдвинуть 1000 на 4 разряда влево и вправо. Тема указатели. Препод говорил, что число нужно переводить в двоичную систему, что-то с...

Биты, байты. Циклически сдвинуть на 4 разряда вправо четное число. - C++
В массиве Х чисел типа short обработать каждое число согласно условиям: Циклически сдвинуть на 4 разряда вправо четное число....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,363
13.03.2010, 16:10     Номер двоичного разряда #2
Задача решается в два шага:
1. Подсчитать общее количество единиц в числе. Гуглить книгу "Алгоритмические трюки для программистов", там есть быстрый и эффективный алгоритм подсчета. Но даже в самом тупом случае - достаточно цикла для подсчета сдвигом числа вправо.
2. Определяешь, сколько разрядов составляет половина - т.е. "число единичных разрядов справа от него равно числу единичных разрядов слева от него". Ну и ищешь опять таки тупым сдвигом числа вправо и анализом единичных битов эту половину....
Где-то так.
Задрот С
0 / 0 / 0
Регистрация: 19.09.2009
Сообщений: 57
13.03.2010, 16:26  [ТС]     Номер двоичного разряда #3
CheshireCat, ну с первым вроде понятно....а со вторым....каким образом можно считать?
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,363
13.03.2010, 20:27     Номер двоичного разряда #4
Ну где-то так (не проверял! это только идея):
C++
1
2
3
4
5
6
7
8
9
int64_t наше_число = .....;
int n = ....; // это сколько единичных разрядов справа надо отсчитать
int count = 0;
while (count <= n)
{
    if (наше_число & 1)
        ++count;
    наше_число >>= 1;
}
outoftime
║XLR8║
507 / 429 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
13.03.2010, 21:40     Номер двоичного разряда #5
Цитата Сообщение от Задрот С Посмотреть сообщение
Для длинного целого числа N определить, если возможно, номер двоичного разряда, для которого выполняется условие: число единичных разрядов справа от него равно числу единичных разрядов слева от него.
А мне кажется ключевое слово здесь - длинного целого числа N, следовательно - длинная арифметика

Добавлено через 1 минуту
Хотя, если я не ошибаюсь, проще будет работать со строками. Но число все ровно нужно будет перевести с 10 в 2 запись, могу подкинуть код для перевода 10-ого представления в 2-е
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,363
13.03.2010, 22:33     Номер двоичного разряда #6
Ну, короткая ли там будет арифметика, длинная или сверхдлинная - это уже детали....... к самому алгоритму не имеющие никакого отношения; точнее, алгоритм должен работать при любой "длине арифметики".
outoftime
║XLR8║
507 / 429 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
14.03.2010, 09:49     Номер двоичного разряда #7
a_in_b.cpp
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include "my.hpp"
 
using namespace std;
 
//опис констант-----------------------------------------------------------------
const int base = 1000*1000;         //база числа в довгій арифметиці
 
//опис функцій------------------------------------------------------------------
void Menu();
void Notation(string &, int &, int &);
vector <int> NotationFrom(string, int &);
vector <int> NotationTo(vector <int>, int &);
string NotationDiv(string, int &, int &);
vector <int> Div(vector <int>, int, int &);
vector <int> Mult(vector <int>, int);
vector <int> Sum(vector <int>, vector <int>);
 
//MAIN()------------------------------------------------------------------------
int main()
{
    Menu();
    return 0;
}
 
//меню програми----------------------------------------------------------------
void Menu()
{
    while (1)
    {
        int from, to;
        string s;
        cout << "Введiть початкову систему числення [2..36]: ";
        while( !(from = Check()) ) cout << "помилка введення\n\nспробуйте ще раз: ";
        cout << "\nВведiть кiнцеву систему числення [2..36]:   ";
        while( !(to = Check()) ) cout << "помилка введення\n\nспробуйте ще раз: ";
        cout << "\nВведiть число:                              ";
        cin >> s;
        cout << endl;
 
        Notation(s, from, to);
            
        if (my::exit()) break;
    }
}
 
//основна функція---------------------------------------------------------------
void Notation(string &s, int &from, int &to)
{
    //переводимо цілу частину в десяткову систему числення
    vector <int> res;
    Up(s);
    int count = 0;
    FOR(i,0,s.size()) 
        if ( !IsPoint(s[i]) ) ++count;
        else break;
    res = NotationFrom(s.substr(0,count), from);
    cout << "Десяткове представлення:\n";
    for (int i(res.size()-1); i > -1; --i)
        cout << res[i];
 
    //переводимо дробову частину в десяткову систему числення
    double dd = 0,
        base = 1;
    int ok = (s[0] == '0'); //перевірка на наявність цілої частини
    string ds = "", d = "";
    if (count < s.size())
    {
        s = s.substr(count+1, s.size()-count);
        FOR(i,0,s.size())
            dd += (base /= from) * (s[i] - '0');
        FOR(i,0,10)
        {
            ds += int(dd *= 10) + '0';
            dd -= int(dd);
        }
        Normalization(ds);
        if(ds.size()) cout << "." << ds << endl;
        d = NotationDiv(s, from, to);
    }
    
    //переводимо число в бажану систему числення
    cout << "\n\nПредставлення числа в системi з основою " << to << ":" << endl;
    res = NotationTo(res, to);
    s.clear();
    for (int i(res.size()-1); i > -1; --i)
        s += ( (res[i]/10) ? (res[i] - 10 + 'A') : (res[i] + '0') );
    s += "." + d;
    Normalization(s);
 
    cout << (s[0] == '.' ? "0" : "") << s << endl << endl;
}
 
//функція для переведення числа в 10-ву систему числення------------------------
vector <int> NotationFrom(string s, int &from)
{
    vector <int> res, d, b;
    res.push_back(0);
    b.push_back(1);
    for (int i(s.size()-1); i > -1; --i)
    {
        d.clear();
        d = Mult(b, (isalpha(s[i])) ? (int(s[i] - 'A') + 10) : (int(s[i] - '0')));
        res = Sum(res, d);
        b = Mult(b, from);
    }
    return res;
}
 
//функція для переведення числа в систему числення з основою 2..36--------------
vector <int> NotationTo(vector <int> a, int &to)
{
    vector <int> res;
    int carry = 0;
    while (a.size() != 1 || (a.back() != 0 && a.size() == 1) )
    {
        a = Div(a, to, carry);
        res.push_back(carry);
    }
    return res;
}
 
//переведення дробової частини числа
string NotationDiv(string s, int &from, int &to)
{
    string res = "";
    double d = 0, base = 1;
    FOR(i,0,s.size())   
        d += (base /= from) * (s[i] - '0');
    FOR(i,0,10)
    {
        res += int(d *= to) + '0';
        d -= int(d);
    }
    return res;
}
 
//ділення довгого на коротке, повернення результуючого вектора на остачі--------
vector <int> Div(vector <int> a, int b, int &carry)
{
    carry = 0;
    for (int i = (a.size()-1); i > -1; --i)
    {
        long long cur = carry * base + a[i];
        a[i] = int (cur / b);
        carry = int (cur % b);
    }
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}
 
//множення довгого на коротке, повернення результуючого вектора-----------------
vector <int> Mult(vector <int> a, int n)
{
    int carry = 0;
    for (int i = 0, _n(a.size()); i < _n || carry; ++i)
    {
        if (i == a.size()) a.push_back(0);
        long long cur = carry + a[i] * n;
        a[i] = (int) cur % base;
        carry = (int) cur / base;
    }
    return a;
}
 
//додавання 2-ох довгих, повернення результуючого вектора-----------------------
vector <int> Sum(vector <int> a, vector <int> b)
{
    if (a.size() < b.size()) swap(a,b);
    int carry = 0;
    for (int i = 0, _n(a.size()); i < _n || carry; ++i)
    {
        if (i == a.size())
            a.push_back(0);
        if (i == b.size())
            b.push_back(0);
        long long cur = a[i] + b[i] + carry;
        a[i] = (int) cur % base;
        carry = (int) cur / base;
    }
    return a;
}

my.hpp
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <windows.h>
#include <conio.h>
 
#define FOR(i,a,b) for (int i = a, _n(b); i < _n; ++i)
#define ABS(a) ( (a) < 0 ? -(a) : a )
 
//оголошення констант ----------------------------------------------------------
const int tSleep = 1500;        //час затримки
 
//перевантаження операторів введення -------------------------------------------
std::ostream &operator << (std::ostream &cout, const char text[])
{
    char *s = new char [strlen(text)+1];
    CharToOem(text, s);
    cout.write(s,strlen(s));
    return cout;
}
 
std::ostream &operator << (std::ostream &cout, const char text)
{
    const char s[] = {text,'\0'};
    char *ds = new char [2];
    CharToOem(s, ds);
    cout.write(ds,strlen(ds));
    return cout;
}
 
//меня виходу ------------------------------------------------------------------
namespace my
{
    int exit()
    {
        int exit = 0;
        while (exit != '2')
        {
            std::cin.clear();
            std::cout << "Виберiть дiю:\n\n"
                     "1 - вийти\t"
                     "2 - продовжити\n";
            exit = getch();
            if (exit == '1')
            {
                system("cls");
                std::cout << "завершення..";
                Sleep(tSleep);
                return 1;
            }
            if (exit != '2')
            {
                system("cls");
                std::cout << "\nПомилка введення\t"
                         "спробуйте ще раз ";
                Sleep(tSleep);
            }
            system("cls");
        }
        return 0;
    }
}
 
//==============================================================================
 
//                            додаткові функції
 
//==============================================================================
 
//перевірка символа на належність "." ------------------------------------------
inline int IsPoint(char &s) { return s == '.'; }
 
//перевірка чи являеться стрічка цілим числом-----------------------------------
int IsDigit(std::string &s)
{
    FOR(i,0,s.size()) if (s[i] < '0' || s[i] > '9') return 0;
    return 1;
}
 
//перевірка на допустимий діапазон значень для систем числення -----------------
int Check()
{
    std::string s;
    std::cin >> s;
    std::stringstream tmp;
    tmp << s;
    int res;
    tmp >> res;
    return (res <= 36 && res >= 2 && IsDigit(s)) ? (res) : (0);
}
 
//переведення стрічки у верхній регістр-----------------------------------------
void Up(std::string &s) { FOR(i,0,s.size()) if (isalpha(s[i])) s[i] += (s[i] >= 'a') ? ('A'-'a') : (0); }
 
//нормалізація стрічки
void Normalization(std::string &s)
{
    int count = 0;
    while (s[s.size()-count-1] == '0') ++count;
    if ( s[s.size()-count-1] == '.') ++count;
    s = s.substr(0, s.size() - count);
}

Специально ничего не менял, что-бы сам разобрался что к чему..

Добавлено через 2 минуты
полсе перевода 2 2-ичную можеш перевести число в строку и пробежав по ней сказать сколько слева и справа стоит 1 или 0 (но этот вариант канает только при очень малых ограничениях, т.к. работать будет долго..)
Задрот С
0 / 0 / 0
Регистрация: 19.09.2009
Сообщений: 57
14.03.2010, 14:01  [ТС]     Номер двоичного разряда #8
outoftime, если не сложно подкинь))буду благодарен)
outoftime
║XLR8║
507 / 429 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
14.03.2010, 14:38     Номер двоичного разряда #9
Номер двоичного разряда
Задрот С
0 / 0 / 0
Регистрация: 19.09.2009
Сообщений: 57
14.03.2010, 16:47  [ТС]     Номер двоичного разряда #10
outoftime, эм..чето там слишком много всего...и коменты на Украинском*(
outoftime
║XLR8║
507 / 429 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
14.03.2010, 20:30     Номер двоичного разряда #11
писал перевод с любой в любую (системы счисления) с любым колычеством цыфр в целой части и 5-ю в дробной (сколько у меня в дроби точно не помню), + это мой курсовой, поэтому здесь много всего и коменты на украинском, кажется все логично
Задрот С
0 / 0 / 0
Регистрация: 19.09.2009
Сообщений: 57
14.03.2010, 21:40  [ТС]     Номер двоичного разряда #12
outoftime, эх..буду пытаться разобраться.....надеюсь получится))лучшебы пояснения правда получить)
outoftime
║XLR8║
507 / 429 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
14.03.2010, 22:10     Номер двоичного разряда #13
Задрот С, ну.. переведи коменты на гугл транслейте, так будет понятно что какая функция делает, а далее - дело техники
Задрот С
0 / 0 / 0
Регистрация: 19.09.2009
Сообщений: 57
15.03.2010, 18:17  [ТС]     Номер двоичного разряда #14
outoftime, спасибо за помощь))проще было самому придумать))))если интересно вот код:

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
#include <stdio.h>
#include <iostream.h>
#include <math.h>
int bitcounter(long int x);
void main()
{
    long int N;
    int i,k,z,f,m[100],l[100];
    i=0;
    f=0;
    printf ("Vvedite znachenie N\n");
    scanf ("%ld",&N);
    z=bitcounter(N);
    if ((k=z%2)==1)
{
    z=z/2+1;
    printf ("Number=%d\n",z);
}
else
    printf ("Net chisla\n");
    for (;N>1;i++)
    {
        k=N;
        N=N/2;
        m[i]=k%2;
    }
    m[i]=N;
    for (;i>=0;i--,f++)
    {
        l[f]=m[i];
    printf ("l=%d\n",l[f]);
    }
}
int bitcounter(long int x)
{
    int counter;
    counter=0;
    while (x!=0)
    {
        counter++;
        x=x>>1;
    }
    return counter;
}
там в принципе сдвиг можно вообще не использовать,но попросили воткнуть чтобы был)))код не красивый,но рабочий)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.03.2010, 18:45     Номер двоичного разряда
Еще ссылки по теме:

Ввести пятизначное число и сдвинуть его циклически вправо на 2 разряда - C++
Ввести пятизначное число и сдвинуть его циклически вправо на 2 разряда (например, ввести число 12345 – получить и вывести 45123).Заранее...

Дано n-значное число longint. Вывести цифры младшего и старшего разряда - C++
Написать программу. Дано n-значное число longint. Провести с ним действия согласно номеру варианта ( 17 ). Вывести только цифры самого...

Напишите программу, считающую сумму старшего и младшего разряда заданного с клавиатуры целого числа. - C++
Напишите программу, считающую сумму старшего и младшего разряда заданного с клавиатуры целого числа.

Число. Вывести только цифры самого младшего и самого старшего разряда - C++
Дано n-значное целое число введеное с клавиатуры. Вывести только цифры самого младшего и самого старшего разряда.

Выяснить номер квартала и номер полугодия по введенному номеру месяца - C++
Вводится число k - номер месяца. Выяснить номер квартала и номер полугодия по введенному номеру месяца. Предвидеть ситуацию неправильного...


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

Или воспользуйтесь поиском по форуму:
outoftime
15.03.2010, 18:45     Номер двоичного разряда
  #15

Не по теме:

Задрот С, неуниверсальный, что главное..

Yandex
Объявления
15.03.2010, 18:45     Номер двоичного разряда
Ответ Создать тему
Опции темы

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