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

@azhankuaku · Регистрация: 18.06.2011

Студворк — интернет-сервис помощи студентам

дано целое число m. получить найбольщее целое k при котором 46^k<m

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

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

@pito211 · 20.06.2011, 08:54

циклом перебери К, чё здесь сложного?

@taras atavin · 20.06.2011, 09:09

Сообщение от 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 · 20.06.2011, 09:32

Сообщение от taras atavin

Нафиг здесь вообще цикл?

ну если человек не додумался до очевидного решения с циклом, то куда уж ему до твоего?

@grizlik78 · 20.06.2011, 09:41

Циклом надёжнее, и не факт, что медленнее.
Надо только возведение в степень организовать сдвигами, учитывая что 4**k = 2**(2*k)
прим.: ** — это степень из другого языка

@taras atavin · 20.06.2011, 09:53

Сообщение от 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 · 20.06.2011, 09:56

Зачем миллиарды? При m=2147483648 потребуется как раз k=31 итераций цикла.

@taras atavin · 20.06.2011, 09:57

Сообщение от grizlik78

потребуется как раз k=31 итераций цикла.

Ты же значение предлагал перебирать, а не показатель степени.

@grizlik78 · 20.06.2011, 09:59

Изначально предлагал перебирать не я. Но, простите, значения чего? Значения k, которые и являются показателями.

@pito211 · 20.06.2011, 10:06

естественно К перебирать, эм же дано

@taras atavin · 20.06.2011, 10:08

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 · 20.06.2011, 10:20

Какая длинная арифметика? Это учебные задачи

Пока есть возможность использовать простые типы, надо их использовать. Пока задачу можно эффективно решить целочисленной арифметикой, это нужно делать.

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 · 20.06.2011, 10:23

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 · 20.06.2011, 10:30

Сообщение от taras atavin

Длинная тоже может быть целочисленной.

Если задача найти целое, и при этом числа не укладываются хотя бы в 64 бита, то никакие ln и pow не спасут. Они не способны хранить такие числа без потери точности. Ну а сдвиги всего числа можно эффективно заменить поиском по массиву. Такой ускоренный "сдвиг"

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

@taras atavin · 20.06.2011, 10:34

Сообщение от grizlik78

Да и для малых чисел в силу особенностей представления вещественных чисел в варианте с ln возможна ошибка

Мантиса в любом случае из одного и того же диапазона значений. И какое минимальное положительное целое существует? А для однёрки эта ошибка уже не возможна в принципе в любом её представлении. ln же и exp можно перегрузить для числел любой разрядности. Вот только сдвигами будет сложнее.

@grizlik78 · 20.06.2011, 10:51

ну хорошо. какой ответ даёт твоя функция (первая, если в ней исправить ошибки, разумеется) при m=262144?

@taras atavin · 20.06.2011, 10:54

8, наверное.

@grizlik78 · 20.06.2011, 10:55

На моей машине твоя функция выдала 9. Объяснять надо, почему? Хотя проверь, возможно на твоей будет всё-таки 8.

@taras atavin · 20.06.2011, 11:05

Это ошибка округления больших чисел, а не малых, но получается, что через дабл нельзя.
А функцию 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;
}

@grizlik78 · 20.06.2011, 11:06

Ну я свою версию выложил. Я в ней уверен.

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@azhankuaku 0 / 0 / 0 Регистрация: 18.06.2011 Сообщений: 9

	Дано целое число m. получить найбольщее целое k при котором 4^k<m 20.06.2011, 08:47. Показов 7364. Ответов 24 Метки нет (Все метки) дано целое число m. получить найбольщее целое k при котором 46^k<m Добавлено через 1 минуту извините есть ошибка вот правильная форма дано целое число m. получить найбольщее целое k при котором 4^k<m 0

@pito211 187 / 174 / 18 Регистрация: 22.03.2010 Сообщений: 612
	20.06.2011, 08:54
	циклом перебери К, чё здесь сложного? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	20.06.2011, 09:41
	Циклом надёжнее, и не факт, что медленнее. Надо только возведение в степень организовать сдвигами, учитывая что 4k = 2(2k) прим.: * — это степень из другого языка 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	20.06.2011, 09:56
	Зачем миллиарды? При m=2147483648 потребуется как раз k=31 итераций цикла. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	20.06.2011, 09:59
	Изначально предлагал перебирать не я. Но, простите, значения чего? Значения k, которые и являются показателями. 0

@pito211 187 / 174 / 18 Регистрация: 22.03.2010 Сообщений: 612
	20.06.2011, 10:06
	естественно К перебирать, эм же дано 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	20.06.2011, 10:51
	ну хорошо. какой ответ даёт твоя функция (первая, если в ней исправить ошибки, разумеется) при m=262144? 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	20.06.2011, 10:54
	8, наверное. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	20.06.2011, 10:55
	На моей машине твоя функция выдала 9. Объяснять надо, почему? Хотя проверь, возможно на твоей будет всё-таки 8. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	20.06.2011, 11:06
	Ну я свою версию выложил. Я в ней уверен. 0