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

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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

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

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