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

#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++

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

#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++

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++

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

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

@taras atavin 4201 / 1793 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	20.06.2011, 10:34	15
	Сообщение от grizlik78 Да и для малых чисел в силу особенностей представления вещественных чисел в варианте с ln возможна ошибка Мантиса в любом случае из одного и того же диапазона значений. И какое минимальное положительное целое существует? А для однёрки эта ошибка уже не возможна в принципе в любом её представлении. ln же и exp можно перегрузить для числел любой разрядности. Вот только сдвигами будет сложнее. 0

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

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

@azhankuaku 0 / 0 / 0 Регистрация: 18.06.2011 Сообщений: 9
		1
	Дано целое число m. получить найбольщее целое k при котором 4^k<m 20.06.2011, 08:47. Показов 5954. Ответов 24 Метки нет (Все метки) дано целое число m. получить найбольщее целое k при котором 46^k<m Добавлено через 1 минуту извините есть ошибка вот правильная форма дано целое число m. получить найбольщее целое k при котором 4^k<m __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

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

@pito211 186 / 173 / 18 Регистрация: 22.03.2010 Сообщений: 612
	20.06.2011, 09:32	4
	Сообщение от taras atavin Нафиг здесь вообще цикл? ну если человек не додумался до очевидного решения с циклом, то куда уж ему до твоего? 0

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

@taras atavin 4201 / 1793 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	20.06.2011, 09:53	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. 0

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

@taras atavin 4201 / 1793 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	20.06.2011, 09:57	8
	Сообщение от grizlik78 потребуется как раз k=31 итераций цикла. Ты же значение предлагал перебирать, а не показатель степени. 0

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

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

@grizlik78 2375 / 1659 / 279 Регистрация: 29.05.2011 Сообщений: 3,387
	20.06.2011, 10:30	14
	Сообщение от taras atavin Длинная тоже может быть целочисленной. Если задача найти целое, и при этом числа не укладываются хотя бы в 64 бита, то никакие ln и pow не спасут. Они не способны хранить такие числа без потери точности. Ну а сдвиги всего числа можно эффективно заменить поиском по массиву. Такой ускоренный "сдвиг" Да и для малых чисел в силу особенностей представления вещественных чисел в варианте с ln возможна ошибка (не утверждаю, что она обязательно будет). 0

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

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