| Daredevil |
| Отправлено: 20.04.2004, 14:31 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
Помогите, пожалуйста, реализовать метод множителя на С. Т.е. любое число должно возводиться в целую степень таким образом:
метод множителя основан на разложении n (степени). Если n=pq, где р представляет собой наименьший простой множитель n, и q>1, x в степени n можно найти, вычислив х в степени р, и возведя эту величину в степень q. Если n — простое число, можно вычислить х в степени n-1, и умножить его потом на х. При n=1, получаем х в степени n без вычислений. Неоднократно применяя эти правила, можно получить формулу вычисления х в степени n при любом целом значении n.
Например, чтобы найти х в 55, сначала нужно вычислить у=х в 5 = х в 4 * х=
(х в 2) в 2) * х, а затем построить у в 11= (у в 10) * у = (у в 2) в 5) * у. Весь процесс предусматривает выполнение восьми умножений.
очень прошу помогите, т.к. идей нет никаких с реализацией....  |
|
| Gedeon |
| Отправлено: 20.04.2004, 15:53 |
|
Ветеран
Группа: Модератор
Сообщений: 1742
|
Я не пойму, Вам надо возвести какое-то число в какую-то степень? Если так то вот код на С:
| CODE |
#include <math.h>
int x, y;
x=5;
y=3;
int p = pow(x,y); |
Хочу заметить х, у, р могут быть не только int, но и double. А если я неправильно Вас понял, то опишите саму задачу поподробней.
|
|
| Doga |
| Отправлено: 20.04.2004, 20:16 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Как я понял проблема состоит в разложении степени n на множетели.
Необходимо представить n в виде:
n = (2 * k) + m
где k — это результат целочисленного деления n на 2 ( т.е. k = (int)n/2 )
m — это целочисленный остаток от деления n на 2 ( т.е. m = n%2)
Затем таким же образом разложим k:
k = (2 * i) + j
Надеюсь описание смысла i и j уже не нужно 
И т.д., и т.д.. и т.д. ...
Разложение следует продолжать до тех пор пока не получим:
(a = (2 *  + c) <= 3
Вот собственно и всё. 
Тебе осталось только оформить этот бред в код процедуры — а мне лень
В математической библиотеке VCL (Math.hpp) есть специальная функция для возведения числа в целую степень:
Extended __fastcall IntPower(const Extended Base, const int Exponent);
А вот её код:
function IntPower(const Base: Extended; const Exponent: Integer): Extended;
asm
mov ecx, eax
cdq
fld1 { Result := 1 }
xor eax, edx
sub eax, edx { eax := Abs(Exponent) }
jz @@3
fld Base
jmp @@2
@@1: fmul ST, ST { X := Base * Base }
@@2: shr eax,1
jnc @@1
fmul ST(1),ST { Result := Result * X }
jnz @@1
fstp st { pop X from FPU stack }
cmp ecx, 0
jge @@3
fld1
fdivrp { Result := 1 / Result }
@@3:
fwait
end;
Если твоя функция будет работать быстрее чем IntPower, напиши...
|
|
| Doga |
| Отправлено: 20.04.2004, 20:23 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Часть заключительной формулы разложения степени была интертрепирована как смайлик — прошу прощения, вот этот
Следует читать:
| CODE | (a = (2 * b) + c) <= 3
|
|
|
| Георгий |
| Отправлено: 20.04.2004, 20:29 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
Daredevil
асимметричный шифр?
на сайтах, посвящённых криптографии видел исходники...
PS. а это случайно не попытка ли подобрать секретный ключ? |
|
| Doga |
| Отправлено: 21.04.2004, 12:45 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Вот ссылка с реализацией на C:
http://algolist.manual.ru/maths/count_fast...st/fast_exp.php
|
|
| Daredevil |
| Отправлено: 26.04.2004, 20:22 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
нет двоичный способ это не то...
нет, функцией pow пользоваться нельзя... =\
степень и х вводятся с клавиатуры
допустим ввели х = 15, и степень 60. так 60 раскладывается на 2*30, у=х^2, и затем У=у^30=(y^2)^15=(y^2)^14 * y=((y^2)^2)^7)*y... и т.д. пока степень не будет состоять из 2 и 3.
нет, это не попытка подобрать секретный ключ, это надо для получения доступа к экзамену!!! помогите плизззз!!!! |
|
| Daredevil |
 Отправлено: 27.04.2004, 17:26 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
эййй!! ну помогите плиззз!!!!
иначе мне крышка..... |
|
| Gedeon |
| Отправлено: 28.04.2004, 09:32 |
|
Ветеран
Группа: Модератор
Сообщений: 1742
|
Так?
| CODE |
double __fastcall TForm1::MyPow(int x, int y)
{
double Result = x;
while(y!=1){
if(y==(y%2)*2||y==(y%3)*3){
if(y%2==(y%2)*2){
y=y/2;
Result *= Result;
}
else{
y=y/3;
Result *= Result*Result;
}
}
else{
Result *= x;
y -= 1;
}
}
return Result;
} |
|
|
| Daredevil |
| Отправлено: 29.04.2004, 19:25 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
хм.. с int проблематично, т.к. сначала у этой проги идет проверка на ввод, т.е. проверяется что ты ввел, буквы или цифры. Эта проверка уже сделана...
но там x, y это переменные char, потому что не я не знаю что будет введено...
как их потом переделать в инт??????
|
|
| exp |
| Отправлено: 29.04.2004, 21:04 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Нафиг тебе проверять входную строку после того как она введена? Проверяй стазу по нажатию кнопки и разреши только "." и цифры.
Или используй MaskEdit — ввел маску и забыл про недопустимые буквы в числе.
|
|
| exp |
| Отправлено: 29.04.2004, 21:07 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Перевод: StrTofloat()
|
|
| Gedeon |
| Отправлено: 30.04.2004, 08:39 |
|
Ветеран
Группа: Модератор
Сообщений: 1742
|
| QUOTE | Нафиг тебе проверять входную строку после того как она введена? Проверяй стазу по нажатию кнопки и разреши только "." и цифры.
Или используй MaskEdit — ввел маску и забыл про недопустимые буквы в числе. |
А если это консоль? Да и зачем float?
если без использования VCL
Convert a string to double (atof and _wtof), integer (atoi, _atoi64, _wtoi and _wtoi64), or long integer (atol and _wtol).
| CODE |
double atof(
const char *string
);
double _wtof(
const wchar_t *string
);
int atoi(
const char *string
);
__int64 _atoi64(
const char *string
);
int _wtoi(
const wchar_t *string
);
__int64 _wtoi64(
const wchar_t *string
);
long atol(
const char *string
);
long _wtol(
const wchar_t *string
);
|
|
|
| Daredevil |
| Отправлено: 06.05.2004, 09:57 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
вот если честно, я не понял что это за маски...
насчет нафиг проверять: в задании так сказано
последний код Гедеона я вообще не понял...понял, только что он конвертит строку в тип double, integer, long integer...
Это моя прога на данный момент, пока она только проверяет правильность ввода, чтобы он снова посылал запрос, когда введена строка, а не число.
#include
#include
int test (char *str, int len) {
int b=0;
for (int i=0; i
{
if ( (int)str[i] < 48 || (int)str[i]> 57 ) b = 1; //48, 57 -коды в Аски таблицее,48 — 0, 57 — 9
}
return b;
}
void main ()
{ char x[255];
char stepen[255];
while (1) {
printf("Vvedite X \n");
scanf("%s", &x);
if (test(x, strlen(x))) { printf("Vi vveli Bukvu \n");}
else { printf ("Vi vveli Chislo \n"); break; }
}
while (1) {
printf("Vvedite Stepen \n");
scanf("%s", &stepen);
if (test(stepen, strlen(stepen))) { printf("Vi vveli Bukvu \n");}
else { printf ("Vi vveli Stepen! \n"); break; }
}
printf("%s, %s", x, stepen);
MyPow(x, stepen);
getchar();
getchar();
}
а как вклинить то эту функцию вычисления сюда? |
|
| Gedeon |
| Отправлено: 06.05.2004, 10:16 |
|
Ветеран
Группа: Модератор
Сообщений: 1742
|
| QUOTE (Daredevil @ 06/05/2004, 10:59) | последний код Гедеона я вообще не понял...понял, только что он конвертит строку в тип double, integer, long integer...
а как вклинить то эту функцию вычисления сюда? |
Это не мой код, а кусок мсдн, то же есть и в стандартном хэлпе.
Пользоваться этими функциями так:
| CODE |
int X = atoi(x);
int Y = atoi(y);
double Otvet = MyPow(X,Y); // или просто сюда вставляйте тело функции
|
Одного я не пойму, как вы будете сдавать экзамен?
|
|
| Daredevil |
| Отправлено: 08.05.2004, 13:48 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 22
|
нет, нам надо написать функцию чтобы она как раз это и вычисляла, а не пользвоваться стандартами...
помогите плиизззз!!!!! |
|
| Gedeon |
| Отправлено: 11.05.2004, 09:28 |
|
Ветеран
Группа: Модератор
Сообщений: 1742
|
| QUOTE (Daredevil @ 08/05/2004, 14:50) | нет, нам надо написать функцию чтобы она как раз это и вычисляла, а не пользвоваться стандартами...
помогите плиизззз!!!!! |
Не понял вам что надо самостоятельно написать функцию преобразования из char в int? Тогда за ассэмблер. Если все до сих пор так плохо приведите Ваш код заключенный в тэги [CODE][/CODE], тогда подставлю эту функцию вам.
|
|
