Дано целое число 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

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

Новые блоги и статьи Все статьи Все блоги /
Вывод данных через динамический список в справочнике Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .

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

	Дано целое число m. получить найбольщее целое k при котором 4^k<m 20.06.2011, 08:47. Показов 7452. Ответов 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