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

Дано целое число m. получить найбольщее целое k при котором 4^k<m - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
azhankuaku
0 / 0 / 0
Регистрация: 18.06.2011
Сообщений: 9
20.06.2011, 08:47     Дано целое число m. получить найбольщее целое k при котором 4^k<m #1
дано целое число m. получить найбольщее целое k при котором 46^k<m

Добавлено через 1 минуту
извините есть ошибка вот правильная форма


дано целое число m. получить найбольщее целое k при котором 4^k<m
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.06.2011, 08:47     Дано целое число m. получить найбольщее целое k при котором 4^k<m
Посмотрите здесь:

C++ Найти наименьшее целое число K, при котором выполняется неравенство 3K > N
Получить наибольшее целое k, при котором 4k < m C++
C++ Дано целое число n. Получить все простые делители этого числа
Дано целое число N (> 0). Найти сумму N2 + (N + 1)2+ (N + 2)2+ … + (2*N)2 (целое число) C++
C++ Составить функцию, которая, получив целое число определяет, уменьшается ли оно в целое число раз
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.06.2011, 08:54     Дано целое число m. получить найбольщее целое k при котором 4^k<m #2
циклом перебери К, чё здесь сложного?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 09:09     Дано целое число m. получить найбольщее целое k при котором 4^k<m #3
Цитата Сообщение от pito211 Посмотреть сообщение
циклом перебери К, чё здесь сложного?
Нафиг здесь вообще цикл?
C++
1
2
3
4
5
6
7
8
9
10
#include <math.h>
int k(int m)
{
 int result=(int)(ln((double)m)/ln(4.0));
 if (m==((int)(exp(((double)result)*ln(4.0))))))
 {
  --result;
 }
 return result;
}
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.06.2011, 09:32     Дано целое число m. получить найбольщее целое k при котором 4^k<m #4
Цитата Сообщение от taras atavin Посмотреть сообщение
Нафиг здесь вообще цикл?
ну если человек не додумался до очевидного решения с циклом, то куда уж ему до твоего?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 09:41     Дано целое число m. получить найбольщее целое k при котором 4^k<m #5
Циклом надёжнее, и не факт, что медленнее.
Надо только возведение в степень организовать сдвигами, учитывая что 4**k = 2**(2*k)
прим.: ** — это степень из другого языка
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 09:53     Дано целое число m. получить найбольщее целое k при котором 4^k<m #6
Цитата Сообщение от grizlik78 Посмотреть сообщение
Циклом надёжнее, и не факт, что медленнее.
Надо только возведение в степень организовать сдвигами,
Эйси. m=65535. k=7. Я предлаю три раз вычислиль логарифмы и один раз степень, а ты перебрать 65536 шагов цикла. А если ещё и лонг, то ещё смешнее. m=2147483648, k=31. У тебя будет более миллиарда шагов цикла, а у меня всего четыре вызова вещественных функций, построенных хоть и на циклах, но на более экономных по членам разложения в ряд. Пусть даже там по 128 шагов, всё равно на четыре вызова набёрётся от силы 512. И x<<2 - это x^4, а не 4^x. И если человек теряется даже в таком простом алгоритме, то циклом тем более будут глюки, так как требуется найти наибольшее k, при котором 4^k<m, а не наименьшее, при котором 4^k>=m.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 09:56     Дано целое число m. получить найбольщее целое k при котором 4^k<m #7
Зачем миллиарды? При m=2147483648 потребуется как раз k=31 итераций цикла.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 09:57     Дано целое число m. получить найбольщее целое k при котором 4^k<m #8
Цитата Сообщение от grizlik78 Посмотреть сообщение
потребуется как раз k=31 итераций цикла.
Ты же значение предлагал перебирать, а не показатель степени.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 09:59     Дано целое число m. получить найбольщее целое k при котором 4^k<m #9
Изначально предлагал перебирать не я. Но, простите, значения чего? Значения k, которые и являются показателями.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.06.2011, 10:06     Дано целое число m. получить найбольщее целое k при котором 4^k<m #10
естественно К перебирать, эм же дано
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 10:08     Дано целое число m. получить найбольщее целое k при котором 4^k<m #11
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int degree(int a, int n)
{
 int reslut, i,b;
 for (result=0, b=1, i=0; i<sizeof(n)*8; ++i)
 {
  if (n&b)
  {
   result+=b;
  }
 }
 return result;
}
int k(int m)
{
 int result;
 for (result=1, b=4; degree(4,result); ++result); 
 return result-1;
}
. Я пишу проги с 1995-го года, а на c++ с 2001-го, но даже я не уверен в правильности.

Добавлено через 1 минуту
Цитата Сообщение от pito211 Посмотреть сообщение
естественно К перебирать, эм же дано
Прогнал. Но на длинной арифметике так и будет. Я как пытался сделать числа килобайтной разрядности, так вот, там будет до восьми тысячь ста девяносто одного шага.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 10:20     Дано целое число m. получить найбольщее целое k при котором 4^k<m #12
Какая длинная арифметика? Это учебные задачи
Пока есть возможность использовать простые типы, надо их использовать. Пока задачу можно эффективно решить целочисленной арифметикой, это нужно делать.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
unsigned max_pow_4(unsigned m)
{
    unsigned k = 0;
    unsigned deg = 1;
    while ( (deg <<= 2) < m && deg)
        ++k;
    return k;
}
 
int main()
{
    unsigned m = 12345;
    unsigned k = max_pow_4(m);
    printf ("m = %u\n", m);
    printf ("k = %u\n", k);
    printf ("4**%u = %u\n", k, 1 << (2*k));
    printf ("4**%u = %u\n", k+1, 1 << (2*(k+1)));
    return 0;
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 10:23     Дано целое число m. получить найбольщее целое k при котором 4^k<m #13
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int degree(int a, int n)
{
 int reslut, i,b;
 for (result=0, b=1, i=0; i<sizeof(n)*8; ++i)
 {
  if (n&b)
  {
   result+=b;
  }
 }
 return result;
}
int k(int m)
{
 int result;
 for (result=1, b=4; degree(4,result); ++result); 
 return result-1;
}
. Я пишу проги с 1995-го года, а на c++ с 2001-го, но даже я не уверен в правильности.

Добавлено через 1 минуту
Цитата Сообщение от pito211 Посмотреть сообщение
естественно К перебирать, эм же дано
Прогнал. Но на длинной арифметике так и будет. Я как то пытался сделать числа килобайтной разрядности, так вот, там будет до восьми тысячь ста девяносто одного шага. Хотя, в логарифме с экспонентой тоже будет много шагов. Но формулой надёжнее.

Добавлено через 39 секунд
Цитата Сообщение от grizlik78 Посмотреть сообщение
Пока задачу можно эффективно решить целочисленной арифметикой, это нужно делать.
Длинная тоже может быть целочисленной.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 10:30     Дано целое число m. получить найбольщее целое k при котором 4^k<m #14
Цитата Сообщение от taras atavin Посмотреть сообщение
Длинная тоже может быть целочисленной.
Если задача найти целое, и при этом числа не укладываются хотя бы в 64 бита, то никакие ln и pow не спасут. Они не способны хранить такие числа без потери точности. Ну а сдвиги всего числа можно эффективно заменить поиском по массиву. Такой ускоренный "сдвиг"
Да и для малых чисел в силу особенностей представления вещественных чисел в варианте с ln возможна ошибка (не утверждаю, что она обязательно будет).
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 10:34     Дано целое число m. получить найбольщее целое k при котором 4^k<m #15
Цитата Сообщение от grizlik78 Посмотреть сообщение
Да и для малых чисел в силу особенностей представления вещественных чисел в варианте с ln возможна ошибка
Мантиса в любом случае из одного и того же диапазона значений. И какое минимальное положительное целое существует? А для однёрки эта ошибка уже не возможна в принципе в любом её представлении. ln же и exp можно перегрузить для числел любой разрядности. Вот только сдвигами будет сложнее.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 10:51     Дано целое число m. получить найбольщее целое k при котором 4^k<m #16
ну хорошо. какой ответ даёт твоя функция (первая, если в ней исправить ошибки, разумеется) при m=262144?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 10:54     Дано целое число m. получить найбольщее целое k при котором 4^k<m #17
8, наверное.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 10:55     Дано целое число m. получить найбольщее целое k при котором 4^k<m #18
На моей машине твоя функция выдала 9. Объяснять надо, почему? Хотя проверь, возможно на твоей будет всё-таки 8.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.06.2011, 11:05     Дано целое число m. получить найбольщее целое k при котором 4^k<m #19
Это ошибка округления больших чисел, а не малых, но получается, что через дабл нельзя.
А функцию degree как проверить?

Добавлено через 1 минуту
Одна ошибка, кстати, есть. В заголовке цикла.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int degree(int a, int n)
{
 int result, i,b;
 for (result=0, b=a, i=0; i<sizeof(n)*8; ++i)
 {
  if (n&b)
  {
   result+=b;
  }
 }
 return result;
}
int k(int m)
{
 int result;
 for (result=1, b=4; degree(4,result)<m; ++result); 
 return result-1;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.06.2011, 11:06     Дано целое число m. получить найбольщее целое k при котором 4^k<m
Еще ссылки по теме:

C++ Дано целое число N. Получить число M, у которого порядок цифр обратный по отношению к N
C++ Циклы с предусловием и с постусловием: получить наибольшее целое k, при котором 4k<N
Получить наибольшее целое k при котором 4^k<m C++

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 11:06     Дано целое число m. получить найбольщее целое k при котором 4^k<m #20
Ну я свою версию выложил. Я в ней уверен.
Yandex
Объявления
20.06.2011, 11:06     Дано целое число m. получить найбольщее целое k при котором 4^k<m
Ответ Создать тему
Опции темы

Текущее время: 23:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru