#c_sharp #числа #double
Рассчитываю pi 3.141592653589794 - это я вижу в отладчике 3.14159265358979 - это, когда вывожу Как мне вывести число полностью?
Ответ 1
Советую ознакомиться с вариантами форматирования вещественных чисел. Для вашего случая подходит описатель формата "R", который гарантирует идентичное число при обратном преобразовании (double.Parse()) Console.WriteLine(pi.ToString("R"));
#javascript #числа
На этот вопрос уже даны ответы здесь:
Числа, начинающиеся с нуля, в JavaScript
(2 ответа)
Закрыт 2 года назад.
При записи числа с лишними нулями результат получается неожиданным:
let i = 000042;
console.log(i); // 34
причем разные числа уменьшаются на разные значения.
Как это можно поправить?
Ответ 1
https://developer.mozilla.org/bm/docs/Web/JavaScript/Guide/Grammar_and_types Leading 0 (zero) on an integer literal, or leading 0o (or 0O) indicates it is in octal. Octal integers can include only the digits 0-7. То есть Ноль (или 0о, или 0О) в начале записи числа указывает на то, что число записано в восьмеричном виде. Откуда в Вашем javascript-е берутся числа в такой записи?
#python #числа
Дан кортеж {"34", "76", "0", "532"}
Как вытащить числа из этого кортежа чтобы при выводе имело такой вид?
34, 76, 0, 532
У меня только мысли засунуть в список, потом вытащить, но всё равно есть кавычки,
как от них избавиться?
a = {"34", "76", "0", "532"}
lst=[]
for i in a:
lst.append(i)
print(lst)
['532', '34', '0', '76']
Ответ 1
Как минимум, (если есть уверенность, что в кортеже только числа) можно в список добавлять числа, а не строки, т. е. вместо lst.append(i), добавлять lst.append(int(i)), но есть способ короче: ", ".join(a) Вывод будет '0, 34, 532, 76'Ответ 2
У вас множество, не кортеж. Поэтому порядок элементов не будет сохранен. Вывести можно так print(', '.join(a))Ответ 3
Можно воспользоваться распаковкой аргумента. print(*{"34", "76", "0", "532"}, sep=', ')Ответ 4
Чтобы сделать числа из строк, примените функцию int(). Чтобы применить функцию к всякому элементу кортежи / списка / множества, используйте функцию map(), в которой в качестве первого параметра будет эта функция (без скобок): map(int, а) # a = {"34", "76", "0", "532"} Результатом будет генератор, из которого можете сделать кортеж, список или множество функциями tuple(), list() или set(). Например для print(list(map(int, a))) будет вывод [532, 34, 0, 76] и для for i in map(int, a): # в цикле for list() не нужен print(i) будет вывод 76 0 532 34 или же для for i in map(int, a): print("{:5}".format(i)) # 5 значит число позиций для цифр (может выть другое) будет вывод 76 34 532 0
#javascript #числа
Пытаясь посчитать сумму чисел заметил следующее поведение:
0.7 + 0.2 + 0.1 = 0.99999999...
Почему так происходит понятно из этого ответа.
Что с этим делать, если нужно чтобы ответ получался правильным? В данном случае:
0.7 + 0.2 + 0.1 = 1
Какие есть решения данной проблемы?
Ответ 1
Ошибку вычисления избежать трудно (много танцев с числами). Лучше будет округлять после вычисления. причем можно округлять до целых если мы хотим видеть только целое число. Math.round Но если мы ожидаем увидеть дробное число этот метод не подойдет нужно использовать округление до до разумного знака после запятой. Округления до 10-го знака обычно бывает достаточно, чтобы отсечь ошибку вычислений и при этом получить нужную точность вычислений: (0.1 + 0.2).toFixed(10) но тут мы получаем тип string нужно доработать с помощью parseFloat Резюмируя округление можно делать так: parseFloat((0.1 + 0.2+0.7).toFixed(10));Ответ 2
Все числа умножить на 10, округлить и просуммировать. Затем результат разделить на 10: (Math.round(n1*10) + Math.round(n2*10) + ... + Math.round(nn*10)) / 10
#python #python_3x #числа
В Python есть встроенный модуль поддерживающий точные вычисления с рациональными числами: from fractions import Fraction print(Fraction(2, 3) + Fraction(5, 7)) Все здорово, если учитывать, что питон по умолчанию использует длинную арифметику. Мне недавно понадобилось использовать комплексные числа только с рациональными мнимой и действительной частями. Вот что из этого вышло: >>> from fractions import Fraction >>> print(Fraction(2, 3) + Fraction(5, 7) * 1j) (0.6666666666666666+0.7142857142857143j) >>> print(complex(Fraction(2, 3), Fraction(5, 7))) (0.6666666666666666+0.7142857142857143j) Fraction автоматически приводится к float. Как решить проблему? В C++, например, можно было бы сделать следующим образом: complexz(Fraction(2, 3), Fraction(5, 7)); Нельзя ли нечто подобное сделать в Python? Я пока, что вижу только одно решение написать свой класс Complex, но надеюсь есть решение проще.
Ответ 1
Боюсь, что другого способа действительно нет. Единственное что, хорошим тоном будет наследоваться от абстрактного класса Complex https://docs.python.org/3.5/library/numbers.html. Это не даст упустить какие-то важные методы и в итоге позволит сделать класс с интерфейсом идентичным оригинальному.
#cpp #python #алгоритм #строки #числа
Дано число, в записи которого может присутствовать до 10^5 цифр. В
этом числе можно поменять любые две цифры местами. Среди всех этих
замен нужно найти ту, при которой получается наибольшее число.
За O(n²) решается легко. Как решить за O(n) или за O(n⋅log(n))?
Примеры:
1234 => 4231
9997754321 => 9997754321
Ответ 1
Запишем цифры первоначального числа в массив a. (Если цифр у числа много, то скорее всего число вам уже дано именно в таком виде.) Скопируем массив в массив b и отсортируем его в порядке убывания. Найдём первый индекс такой, что a[i] != b[i]. Если такого индекса нет, перестановка не нужна, порядок оптимальный. Пусть это индекс k. Очевидно, b[k] >= a[i] для i >= k, причём b[k] != a[k] по выбору k. Значит, b[k] — максимальное из оставшихся чисел. Очевидно, b[k], b[k+1], ... — перестановка чисел a[k], a[k+1], ..., поэтому b[k] == a[l] для некоторого l > k. (l != k, т. к. b[k] != a[k]). Возьмём наибольшее такое l. Перестановка индексов k и l — искомая. Сложность: O(n log n) { сортировка } + O(n) { поиск k } + O(n) { поиск l } = O(n log n). Обновление: Поскольку мы сортируем цифры, то сложность сортировки можно уменьшить до O(n), применив сортировку подсчётом. Итоговая сложность O(n). Примечание: Можно избавится от дополнительного массива b, если заменить его просто на количество 9-ок, 8-ок, 7-ок и т. д. (эта информация используется в сортировке подсчётом), за счёт некоторого усложнения кода. Таким образом мы получаем всего лишь O(1) дополнительной памяти.Ответ 2
Вот реализация на Питоне линейного (O(n)) алгоритма c постоянной дополнительной памятью (O(1)), описанного в ответе @VladD: #!/usr/bin/env python3 from collections import Counter def make_largest_by_swapping_2_digits(digits): """O(n) time, O(m) space""" # find where given number differs from the largest number with the same digits multiplicity = Counter(digits) # count how many times each digit occurs all_digits = sorted(multiplicity, reverse=True) # m digits in decreasing order largest = (d for d in all_digits for _ in range(multiplicity[d])) for k, (a, b) in enumerate(zip(digits, largest)): if a != b: break else: # already largest possible return # nothing to swap # find on the right where a == b j = next(len(digits) - i for i, a in enumerate(reversed(digits), 1) if a == b) digits[k], digits[j] = digits[j], digits[k] # swap Пример: digits = [1,2,3,4] print('before', *digits) make_largest_by_swapping_2_digits(digits) print('after ', *digits) Результат before 1 2 3 4 after 4 2 3 1 Заметки по коду: Counter() просто считает сколько раз каждая цифра встречается: print(Counter(str(9997754321))) # -> Counter({'9': 3, '7': 2, '5': 1, '4': 1, '3': 1, '2': 1, '1': 1}) Потребление памяти O(m), где m не более 10 для десятичной системы. Можно считать константой. Counter по сути multiset здесь (набор цифр с повторениями). Если ограничить тип цифр только целыми десятичными, то можно простой массив использовать вместо Counter: multiplicity = [0] * 10 for d in digits: multiplicity[d] += 1 largest это наибольшее число, составленное из тех же цифр что и входное число. Для представления используется генератор, поэтому дополнительная память нужна только для одной цифры в каждый момент O(1) enumerate(zip()) позволяет обойти две последовательности одновременно по одной паре элементов за раз, отслеживая текущий индекс: >>> list(enumerate(zip(range(3), "abc"))) [(0, (0, 'a')), (1, (1, 'b')), (2, (2, 'c'))] make_largest_by_swapping_2_digits(digits) принимает любую изменяемую последовательность (list, bytearray, mmap, etc) c хэшируемыми элементами, которые можно сравнивать. Например, для больших чисел, записанных в файле, можно с mmap напрямую работать (предполагая, что отдельная цифра в байте помещается): import mmap with open('много-цифр.txt', 'r+b', 0) as file, \ mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_WRITE) as digits: make_largest_by_swapping_2_digits(digits) После выполнения кода, файл много-цифр.txt будет содержать новое число—изменение по месту происходит.
#алгоритм #математика #числа
Задача. Даны два числа s и p, при этом s <= p. Требуется найти ближайший после s
делитель d числа p, такой что:
s <= d
p mod d = 0
если s != d, то p mod (s,d] != 0 // в дипазоне от s до d нет делителей
Например, для s = 7 и p = 33, d = 11.
Придумал два вот таких варианта:
// тупой перебор
int delimeter_1(int s, int p)
{
if(s <= p)
{
int d = s;
while(0 != p % d)
{
++d;
}
return d;
}
return p;
}
// перебор поумнее
int delimeter_2(int s, int p)
{
if(s <= p)
{
int q = p / s;
while(0 != p % q)
{
--q;
}
return p / q;
}
return p;
}
Пояснение. Например для числа 15 построим таблицу:
делители: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
частное : 15 7 5 3 3 2 2 1 1 1 1 1 1 1 1
остаток : 0 1 0 3 0 3 1 7 6 5 4 3 2 1 0
Так вот, в delimeter_1 мы движемся по строке делители, а в delimeter_2 по строке
частное - второй вариант получается чуть быстрее.
У меня есть подозрение, что возможно есть более быстрое и элегантное решение, основанное
на свойствах чисел, либо вообще без циклов, либо с более короткими циклами. Мне не
обязательно готовое решение, может кто-то подскажет где почитать на близкую тему или
выскажит интресные мысли и замечания.
Подумав, пришел к выводу, что аналитического неитерационного алгоритма не сущетсвует.
Такой алгоритм можно представить в виде некой функции f(q,s) = d, то есть q mod f(q,s)
= 0, или в виде уравнения q mod (s + k) = 0, где s + k = d. Как вытащить k мне не известно,
перешерстил все и ничего не нашел.
Ответ 1
Решая перебором, следует комбинировать оба подхода. Для p/d < d применять первый, для p/d > d второй. Т.е. сначала бежим по делителям, потом по частным. В случае с таблицей по 15 будет от 1 до 4 (по делителю) первый подход, от 3 до 1 (по частным) второй. Для варианта d = 1000 таблица будет из 1000 столбцов, а итераций от 1 до 31 и обратно от 31 до 1 всего 62 (плюс-минус) максимум. Дальше учитываем s и оптимизируем. Т.к. для первого подхода мы пройдем все делители от s до sqrt(p) второй раз при проходе по частным эти делители проходить не нужно, второй подход можно сразу начинать с s и до 1. Получаем простой цикл от 1 до sqrt(p), просто для выявления ближайшего к s делителя порядок не прямой. В итоге: int delimeter_3(int s, int p) { int i = s; while(i > 1) { if(p % i==0) break; if(i >= s) i++ else i--; if(i > sqrt(p)) i = min(s, p / s) - 1; } return i >= s ? i : i ? p / i : p; }Ответ 2
Очевиден тот факт, что в случае нулевого остатка операция деления даёт сразу пару делителей числа p (делитель и частное), причём половина делителей лежит слева от числа q=[sqrt(p)], а половина - справа. При больших p неизбежно q << p, и части (q и p-q) явно неравны, поэтому, к примеру, при факторизации стараются начинать с меньших делителей. Заметим, что при исходных данных (s=3, p=94) нахождение требуемого искомого делителя "в лоб" потребует 91 операцию перебора, в то время как факторизация - всего лишь одну. Причина кроется в низкой эффективности поиска делителей на интервале (q,p), потому что их плотность там мала, а требуемый делитель 2 (который является ключом к частному 47) мы проскочили. Т.е. в случае s < q есть риск превратить поиск делителя в рулетку. Другое дело, если s>>q. Перебирая (в обратном порядке) частные от деления p на t, t-1,...,2, где t = [q/s], мы повышаем шансы найти требуемый делитель. Т.е. в этом случае параметр s может принести пользу. Но что же делать при s < q? В этом случае остаётся выбор - пойти на факторизацию или ограничиться проверкой делителей. Во втором случае можно начать с перебора делителей по возрастанию, начиная с s+1, но перебор на интервале [q,p/s) вести с помошью таблицы неиспользованных частных (в обратном порядке), а на интервале [p/s,p) -- непосредственно вычисляя оставшиеся частные делением p на s, s-1, ....Ответ 3
Вначале надо факторизовать число, потом построить список его делителей, отсортировать его по возрастанию и найти, в какое место попадает s, и взять следующий справа делитель. Факторизовать чем-нибудь отсюда, дальше проще. А перебирать задолбаешься на первом же Р больше миллиона.
#php #числа #php_faq
В документации указано:
PHP не поддерживает беззнаковые целые (integer)
Что это значит: беззнаковые целые?
Я предполагаю, что, например, 1 — беззнаковое; -1 или +1 — со знаком. Но PHP ведь
адекватно работает со всеми тремя вариантами...
Ответ 1
Это не вполне корректная формулировка. Правильная - такая: "PHP не поддерживает беззнаковые целочисленные типы данных". Беззнаковый целочисленный тип данных - это целочисленный тип данных, неспособный хранить отрицательные числа. Обычно в языках программирования со статической типизацией целочисленные типы данных идут парами. Так, в C++11 есть знаковый тип int32_t, вмещающий числа от -2 147 483 648 до 2 147 483 647 - и парный ему беззнаковый тип uint32_t, вмещающий числа от 0 до 4 294 967 295. Но в PHP, как в языке с динамической типизацией, целочисленный тип данных всего один (integer), и он знаковый.
#php #массивы #числа #множества #nlp
Здравствуй, дали задачу по PHP
Напишите массив с числами от 1 до 30
[1, 2, 3 ....]
и функцию, которая делает следующее
проходит по массиву и каждому числу дописывает фразу "новых комментариев" и эти
слова склоняются в соответствии с их числом
и делает в итоге массив
1 новый комментарий
2 новых комментария
и тд
и вывести на экран в
html в элементе
Прошу помочь с примерами решения, в PHP я новичок, теорию изучил не плохо но сижу
несколько дней и не дошло пока что использовать в этом примере.
Ответ 1
Есть статья относительно множественных чисел. Там собраны алгоримы определения множественного числа для многих стран. Алгоритмы представлены в виде формул. Не нужно изобретать велосипед. Мы же используем формулы в математике. В данном случае мы берем русский язык: nplurals=3 То есть для русского языка три множественные формы: 1) Когда элемент один. Например: 1 новый комментарий 2) Когда элементов больше двух, но меньше пяти. Например: 3 комментария, 4 комментария 3) Когда элементов больше или равно пяти. Например: 5 новых комментариев, 6 новых комменариев Теперь перейдем к реализации. Условия привел в более читаемый вид: $numbers = ['1', '2', '3', '4', '5']; function plural($number) { if ($number % 10 == 1 && $number % 100 != 11) { return $number . ' новый комментарий'; } else { if ($number % 10 >= 2 && $number % 10 <= 4 && ($number % 100 < 10 || $number % 100 >= 20)) { return ($number . ' новых комментария'); } else { return ($number . ' новых комментариев'); } } } foreach ($numbers as $number) { echo plural($number); echo '
'; }Ответ 2
На мой взгляд самое элегантное решение функции plural такое: function plural($number, $array){ $keys = [2, 0, 1, 1, 1, 2]; return $array[$number % 100 > 4 && $number % 100 < 20 ? 2 : $keys[min($number % 10, 5)]]; } Как это работает: Есть массив со склонениями $array[' новый комментарий', ' новых комментария', ' новых комментариев'] Cоставляем массив ключей $keys = [2, 0, 1, 1, 1, 2]; $keys[0] = 2; → $array[2] = 'новых комментариев' → 0, 20, 30, 10020... 'новых комментариев' $keys[1] = 0; → $array[0] = 'новый комментарий' → 1, 21, 31... 'новый комментарий' $keys[2] = $keys[3] = $keys[4] = 1; → $array[1] = 'новых комментария' → 2, 3, 4, 31, 32, 33, 34 ... 'новых комментария' $keys[5] = 2; → после 5-х всегда 'новых комментариев' → 5 'новых комментариев', 1006 'новых комментариев' Поэтому $array[$keys[min($number%10, 5)]]; На этом бы можно было закончить, НО...есть 11, 12, 13 'новый комментарий' — это исключение. Запишем $number % 100 > 4 && $number % 100 < 20 ? 2 Итак, разобрались с выражением $number%100 > 4 && $number%100 < 20 ? 2: что если остаток отделения в пределах 4–20, то всегда - новых комментариев. Теперь составляем массив с элементами массива, а потом просто в цикле обходим весь массив и конкатенируем его значение. $arrays = [1,2,3,4,5,6,7,8,9,10]; foreach($arrays as $key=>$val) { $arrays[$key] .= plural($val, array(' новый комментарий', ' новых комментария', ' новых комментариев')); } var_dump($arrays); Обновлено Почему такой порядок ключей? $keys = [2, 0, 1, 1, 1, 2]; Есть массив ключей $keys = [2, 0, 1, 1, 1, 2]; и массив склонений $array[' новый комментарий', ' новых комментария', ' новых комментариев']. Для простоты рассмотрим значения от 0- 10: 0 - $keys[0] = 2, а $array[2] = "..ев"; 1 - $keys[1] = 0, а $array[0] = "..й"; 2 - $keys[2] = 1, а $array[1] = "..я"; 3 - $keys[3] = 1, а $array[1] = "..я"; 4 - $keys[4] = 1, а $array[1] = "..я"; а всё что после пяти это будет "...ев"; 5,6,7,8,9 - $keys[5] = 2 $array[2] "..ев"; По такому принципу можно склоняются все числа кроме 11,12,13,14
#python #python_2x #числа
На вход функцией input подается 6-значеное число. Нужно разбить его на на отдельные
числа. Например: 123456 -> 1 2 3 4 5 6. Делается это для того, чтобы проверить эквивалентность
суммы первой и второй тройки чисел (Задача о счастливом билете). В программировании
я начинающий и желательно всё сделать операциями div, mod, if-else
a = int(input())
b = a//1000
one = b//100
two = b%11
three = b%10
c = a%1000
four = c//100
five = c%11
six = c%10
if (one+two+three)==(four+five+six):
print ('Счастливый')
else:
print ('Обычный')
Ответ 1
Можно, конечно, честно посчитать остатки от деления и т.д., но проще всего разбить на символы строку, а потом перевести эти символы обратно в числа. Делается это во второй строке следующей программы: a = 123456 b = map(int, str(a)) print b if len(b)==6: print "Happy" if b[0] + b[1] + b[2] == b[3] + b[4] + b[5] else "Unhappy" Если очень хочется честным образом делить на 10, то можно вторую строку этой программы заменить на такой фрагмент: b = [] while a > 0: b.append(a % 10) a = a // 10 b = b[::-1] # так можно развернуть, если бы нам был важен порядок print b Теперь по тексту Вашей программы: почему-то берётся остаток от деления на 11 (в строках two = b%11 и five = c%11, хотя правильно было бы поделить на 10, а потом взять остаток от деления на 10 (two = (b // 10) % 10). Вам надо разобраться, откуда взялось 11, так как это очень странный код. Дополнение: Если нам важно поддержать случаи входных значений a менее, чем шестизначных, то можно поменять всего одну строчку: while len(b) < 6: # теперь в b заведомо будет 6 элементов Также рекомендую изучить код из соседнего ответа (от jfs), так как в нём есть ряд интересных моментов.Ответ 2
Чтобы найти сумму цифр числа, заданного в виде строки: def sum_digits(s): return sum(map(int, s)) это идиоматичный способ для данной задачи в Питоне. sum_digits() функцию можно использовать, чтобы определить является ли заданное число "счастливым": #!/usr/bin/env python3 s = input() middle = len(s) // 2 # середина if middle == 0 or sum_digits(s[:middle]) == sum_digits(s[-middle:]): print('Счастливый') else: print('Обычный') Число считается "счастливым", если сумма цифр левой половины равна сумме цифр правой половины числа. Пустая строка (нет цифр) — в качестве вырожденного случая — также рассматривается "счастливой". Если хочется, можно использовать деление, чтобы разбить неотрицательное целое число на отдельные цифры: def digits_recursive(n, digits=[]): return digits_recursive(n // 10, [n % 10] + digits) if n else digits or [0] Пример: >>> digits_recursive(123) [1, 2, 3] Или то же самое, используя явный цикл: def digits_iterative(nonneg): digits = [] while nonneg: digits += [nonneg % 10] nonneg //= 10 return digits[::-1] or [0] Пример: >>> digits_iterative(123) [1, 2, 3] >>> sum(_) 6Ответ 3
Видел это задание во вводном курсе Python до изучения массивов и функций типа map() так что в том случае корректней было вот такое решение. a = int(input()) b = a//1000 one = b // 100 two = b // 10 % 10 three = b % 10 c = a % 1000 four = c // 100 five = c // 10 % 10 six = c % 10 if (one+two+three)==(four+five+six): print ('Счастливый') else: print ('Обычный')Ответ 4
num = list('123321') summ_1 = int(num[0]) + int(num[1]) + int(num[2]) #cумма первых трех summ_2 = int(num[3]) + int(num[4]) + int(num[5]) #cумма последних трех трех
#массивы #алгоритм #числа
Задачка кажется очень простой, но все равно не выходит.
Дан массив целых чисел, упорядоченный строго по возрастанию.
Дано некоторое число X, нужно менее чем за квадратное количество операций(то есть
перебор всех пар) найти такие два любых элемента массива, что их сумма равна X, иначе
вывести 0.
Как сделать это меньше, чем за квадратное время?
Подкиньте идею какую-нибудь, ну или сам подход?))
Спасибо=)
Ответ 1
Решение за О(n): Решаем методом "2 указателя" Храним 2 индекса: первый сначала указывает на нулевой элемент, второй - на последний элемент. Цикл - пока индексы не будут равны (то есть пока они не укажут на один и тот же элемент. Если такое случилось - значит, искомых элементов в массиве нет). На каждой итерации цикла сравниваем текущую сумму (сумму элементов, на которые указывают индексы) с искомой. Если сумма меньше - увеличиваем первый индекс, если сумма больше - уменьшаем второй индекс. Если равна - решение найдено. #include#include using namespace std; int main() { int *a; // массив int n; // количество элементов в массиве int sum; // необходимая сумма /// //чтение массива cin >> n; a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; cin >> sum; /// // индексы int lt = 0; // первый, то есть левый int rt = n - 1; // второй, то есть правый while (lt != rt) { int cursum = a[lt] + a[rt]; if (cursum < sum) lt++; else if (cursum > sum) rt--; else // if (cursum == sum) { cout << "indexes: " << lt << " " << rt << endl; cout << "values: " << a[lt] << " " << a[rt] << endl; return 0; } } cout << "not found" << endl; return 0; } Ответ 2
Поскольку массив отсортирован, то этим фактом можно воспользоваться для поиска второго элемента в паре с помощью бинарного поиска. Алгоритм следующий: Проходим массив, для каждого элемента вычисляем, какая ему нужна пара Ищем эту пару с помощью бинарного поиска Если элемент нашелся и это не текущий элемент, то мы нашли пару Т.о. получим алгоритм со сложностью O(nlogn): цикл дает O(n), бинарный поиск дает O(logn). Примерный код: bool found = false; for (int i = 0; i < array.Length; i++) { int first = array[i]; int second = X - first; // искомый элемент int index = BinarySearch(array, second); if (index > -1 && index != i) { Console.WriteLine("{0} and {1}", i, index); found = true; break; } } if (!found) { Console.WriteLine("No such pairs!"); }Ответ 3
сосчитать необходимые дополнения до X для каждого элемента. Этой операциии не избежать. Получится убывающий ряд. двигаемся по обоим рядам от меньших к большим, пока не находится равенство. Тогда пара найдена – значение и X минус значение. Т.о. один раз пройти, вычисляя дополнения до X, и макс. 2 раза, разыскивая совпадения. И по результатам, исключить дубли зеркальных пар, как (-3,15) в примере ниже. Недостаток – нужно хранилище для 2 x размер данных. Это оптимизируется, но не будем усложнять. Пример: X = 12, исходный ряд: -3 1 3 4 7 9 12 15 -3 1 3 4 7 9 12 15 дополнения до X: 15 11 9 8 5 3 0 -3 двигаем пошагово указатель на текущий элемент в каждом ряду от меньших к большим, если бОльшее значение в одном ряду, в другом ряду берём следующее, если равны, то для след. шага сравнения берём по след. значению в обоих -3 1 3 4 7 8 12 15 -3 0 3 5 8 9 11 15 Находим -3, значит, пара (-3, 12 - -3 = 15); второе совпадение (3, 12-3=9); третье совпадение (15, 12-15=-3); Надо ещё пройтись по результатам и убрать зеркальные дубли пар, если есть (тут один случай). Upd не рассмотрел случай, если дополнение = значению и повтор одинаковых значений в исходном массиве, напр. [1,3,3,4,4].Ответ 4
Цикл К=1 до N-1 Цикл H=K+1 до N Если A[K]+A[H] = X Вывод A[K], A[H] Стоп Если нет пар, Вывод 0 A - Массив N - Количество элементов Тогда через бинарный поиск Цикл К=1 до N-1 M = X - A[K] Бинарный поиск М Если A[K]+М = X Вывод A[K], М Стоп Если нет пар, Вывод 0 в бинарном поиске операций меньше, около log2(n)
#php #cpp #алгоритм #математика #числа
Подскажите, пожалуйста, алгоритм нахождения квадратного корня из числа (не sqrt(a)
и не pow(a, 0.5)), а итерациями, вручную. Ответ должен быть не целочисленным, а точным,
типа float.
Язык - желательно C.
Ответ 1
Можно попробовать метод Ньютона. По сути, чтобы найти корень из числа S, надо решить уравнение f(x) = 0, где Подставляя эту функцию в формулу для итераций метода Ньютона, получаем Я набросал работающую программу на Python, можете по ней ориентироваться: #!/usr/bin/python import sys s = float(sys.argv[1]) x = 1.0 while abs(x * x - s) > 0.00001: x = (x * x + s) / 2. / x print xОтвет 2
Есть бывший школьный алгоритм извлечения квадратного корня столбиком, по типу деления уголком. Сохранён для потомков в Википедии, п.6.6. Алгоритм построен на тождестве (ae+b)2=a2e2 + (2ae+b)b для e=10. В роли a выступает значение квадратного корня, вычисленное для старших цифр числа, в роли b - новая цифра. Значение корня вычисляется по недостатку, количество десятичных цифр результата не ограничено. В отличие от алгоритма деления столбиком, в получении новой цифры участвуют сразу две новых цифры исходного числа, а при получении дробной части нули добавляют тоже парами. Об этом нам говорит множитель e2=100 в формуле. Чтобы результат не получил множитель sqrt(10)=3.162, цифры попарно группируют, начиная от десятичной точки. При этом в самой старшей группе оказываются одна или две цифры. На рисунке (пример из Википедии, рисунок изменён) изображён процесс извлечения квадратного корня из числа N = 69696. Число N размещено привычным образом. Вместо уголка справа мы писали знак =. И почти сразу писали первую цифру b2=a2=2, потому что [sqrt(6)]=2. Это был разряд сотен. На второй итерации рассуждаем так: левая часть тождества - сверху, число a2=2 - справа от знака равенства. Вычитая из верхнего числа величину (a2)2=4 и снося к этой двойке вниз пару цифр 96, мы получаем соотношение (2a2e+b1)b1 = 296, где b1 - неизвестная цифра в разряде десятков. Проводим горизонтальную и вертикальную чёрточки, как на рисунке, и слева от вертикальной черточки с отступом влево на один разряд пишем число 2a2=4. Если дописать справа цифру b1, получим как раз 2a2e+b1. А если эту же цифру b1 подписать внизу, то получим пример на умножение с ответом 296. Подберём эту цифру в уме: 45х5=225 - маловато, 47х7=329 - уже перебор, 46х6=276 - в самый раз! И сразу записываем 276 под 296 - чтобы не забыть. А праведно добытую цифру b1=6 дописываем к ответу справа. Итак, третья итерация. И кое-что уже ясно: две новые чёрточки, вычитание столбиком и снос следующих двух цифр - 2096... А вот и нюанс: (2a2e+b1)+b1=2(a2+b1)=2a1. Т.е. мы не обязаны умножать в уме 26х2, а можем сложить столбиком 46 и 6. И получить 52. Итак, 52b0 x b0 = 2096... b0=4 - ура, сошлось! Аккуратно подрисовываем 4 в умножение, 2096 снизу, 4 справа. Корень извлечён в целости и сохранности нацело. Теперь ничто не мешает формализовать алгоритм, причём для любой системы счисления. Может возникнуть вопрос: зачем этот алгоритм, если есть итерационный алгоритм Герона Александрийского? Просто потому, что у него есть плюсы - такие же, как у деления уголком: Возможность вычисления результата со скоростью ~10 операций (сравнение, вычитание, логическое ИЛИ и сдвиги) на бит результата с аппаратной погрешностью. Удобство применения для длинных двоичных чисел, представленных массивами. Возможность извлечения квадратного корня вручную в любой системе счисления. Гарантированное представление результата по недостатку. Например, для e=2 программа эмулирует аппаратную реализацию квадратного корня для мантиссы числа (программа написана на PHP): function msb($num){ $k = ($num > 65535) ? 16 : 0; // Если левое слово ненулевое, это минимум 16 разрядов. if (($num>>$k) > 255) $k |= 8; // Второй байт после сдвига не 0 - это +8 разрядов. if (($num>>$k) > 15) $k |= 4; // Левая тетрада после сдвига не 0 - это +4 разряда. if (($num>>$k) > 3) $k |= 2; // Левая диада после сдвига не 0 - это +2 разряда if (($num>>$k) > 1) $k |= 1; // Левый разряд после сдвига не 0 - это +1 разряд. return $k; } function sqrt_school($n){ if($n>>31) return null; if($n<1) return 0; $digit_pos = msb($n) >> 1; // текущая позиция бита результата $result = 1 << $digit_pos; // результат // printf ("n= %b digit_pos=%d", $n, $digit_pos); //// $top = $n - ($result<<$digit_pos); // остаток while($digit_pos>0){ $mult = ($result << $digit_pos--) | (1 << ($digit_pos<<1)); // вычитаемое для цифры 1 // printf ("
result=%b digit_pos=%d top=%b mult=%b", $result, $digit_pos, $top, $mult); if($top >= $mult){ $result |= 1 << $digit_pos; // вписали бит в результат $top -= $mult; // уменьшили остаток } // printf(" left=%b",$left); } return $result; } function sqrt_heron($n){ $s = (float)$n; $x = (float)1; while (abs($x*$x - $s) > 0.5) { $x = ($x + $s/$x)/2; } return (int)$x; } for($i=0; $i<10000; $i++){ $test_array[$i] = mt_rand(2,1000); } $time0 = microtime(GET_AS_FLOAT); for($i=0; $i<10000; $i++){ $school = sqrt_school($test_array[$i]); } $time1 = microtime(GET_AS_FLOAT); for($i=0; $i<10000; $i++){ $heron = sqrt_heron($test_array[$i]); } $time2 = microtime(GET_AS_FLOAT); printf("
Test [2,1000]: time_school=%d ns time_heron=%d ns",100*($time1-$time0)+0.5,100*($time2-$time1)+0.5); for($i=0; $i<10000; $i++){ $test_array[$i] = 1000000*mt_rand(2,1000); } $time0 = microtime(GET_AS_FLOAT); for($i=0; $i<10000; $i++){ $school = sqrt_school($test_array[$i]); } $time1 = microtime(GET_AS_FLOAT); for($i=0; $i<10000; $i++){ $heron = sqrt_heron($test_array[$i]); } $time2 = microtime(GET_AS_FLOAT); printf("
Test 1000000000*[2,1000]: time_school=%d ns time_heron=%d ns",100*($time1-$time0)+0.5,100*($time2-$time1)+0.5); for($i=1; $i<3000000000; $i*=3){ $school = sqrt_school($i); $heron = sqrt_heron($i); printf("
sqrt_school($i)=%d sqrt_heron($i)=%d" , $school, $heron); } Попутно проведено сравнение с алгоритмом Герона (замена деления на двойку умножением ничего не даёт). Результаты совпали, по быстродействию в 3-5 раз выигрывает "школьный" алгоритм. Test [2,1000]: time_school=13 ns time_heron=39 ns Test 1000000 * [2,1000]: time_school=19 ns time_heron=90 ns sqrt_school(1)=1 sqrt_heron(1)=1 sqrt_school(3)=1 sqrt_heron(3)=1 sqrt_school(9)=3 sqrt_heron(9)=3 sqrt_school(27)=5 sqrt_heron(27)=5 sqrt_school(81)=9 sqrt_heron(81)=9 sqrt_school(243)=15 sqrt_heron(243)=15 sqrt_school(729)=27 sqrt_heron(729)=27 sqrt_school(2187)=46 sqrt_heron(2187)=46 sqrt_school(6561)=81 sqrt_heron(6561)=81 sqrt_school(19683)=140 sqrt_heron(19683)=140 sqrt_school(59049)=243 sqrt_heron(59049)=243 sqrt_school(177147)=420 sqrt_heron(177147)=420 sqrt_school(531441)=729 sqrt_heron(531441)=729 sqrt_school(1594323)=1262 sqrt_heron(1594323)=1262 sqrt_school(4782969)=2187 sqrt_heron(4782969)=2187 sqrt_school(14348907)=3787 sqrt_heron(14348907)=3787 sqrt_school(43046721)=6561 sqrt_heron(43046721)=6561 sqrt_school(129140163)=11363 sqrt_heron(129140163)=11363 sqrt_school(387420489)=19683 sqrt_heron(387420489)=19683 sqrt_school(1162261467)=34091 sqrt_heron(1162261467)=34091 Из тестов следует также, что увеличение разрядности результата по "школьному" алгоритму не приведёт к серьзному замедлению вычислений.Ответ 3
Да, Вам нужен не целочисленный. Если кому-то интересен целочисленный, то вот (вроде хорощий) из интернета unsigned int sqrt32(unsigned long n) { unsigned int c = 0x8000; unsigned int g = 0x8000; for(;;) { if(g*g > n) g ^= c; c >>= 1; if(c == 0) return g; g |= c; } }
Есть скрипт:
$passport = '28 48 399999';
$passport = str_replace(' ','', $passport);
$passport = intval($passport);
var_dump($passport);
Его dump: int(2147483647)
Вопрос: почему? пробелы убрал, а в число преобразует кое-как...
2 147 483 647 — это 231–1, максимальное целое число, помещающееся в 32 бита. Ваше число 2 848 399 999 больше, поэтому PHP решил преобразовать его к самому близкому значению, которое может быть представлено.
Похапэ искаропки не умеет в длинные целые. Должны быть математические пакеты, если вам это действительно нужно.
Еще давно я наблюдал во ВКонтакте длинные идентификаторы пользователей, например:
Ссылка vk.com/id1 будет эквивалентом vk.com/id4294967297.
Я разобрался лишь в том, что это число 4294967296 это 2^32 степени, еще тот факт, что если брать 2^32 (к примеру) и прибавить к нему свой идентификатор страницы, то мы получаем тот самый длинный ID.
PS. Проверял так же 2^33 и выше по такому же принципу, все так же получается длинные идентификаторы.
Вопрос: откуда берутся такие числа? И как их можно получить не ручным перебором?
Требуется найти числа, которые по модулю 2^32 равны заданному ID.
В общем виде это выглядят так:
ID + (k * 2^32)
Подробнее:
k - неотрицательное целое число (0, 1, 2, 3, ...)
ID - идентификатор пользователя VK
Рассчитываю pi 3.141592653589794 - это я вижу в отладчике 3.14159265358979 - это, когда вывожу Как мне вывести число полностью?
Советую ознакомиться с вариантами форматирования вещественных чисел. Для вашего случая подходит описатель формата "R", который гарантирует идентичное число при обратном преобразовании (double.Parse()) Console.WriteLine(pi.ToString("R"));
На данный вопрос уже ответили:
Числа, начинающиеся с нуля, в JavaScript
2 ответа
При записи числа с лишними нулями результат получается неожиданным:
let i = 000042;
console.log(i); // 34
причем разные числа уменьшаются на разные значения.
Как это можно поправить?
https://developer.mozilla.org/bm/docs/Web/JavaScript/Guide/Grammar_and_types
Leading 0 (zero) on an integer literal, or leading
0o (or 0O) indicates it is in octal. Octal integers can include only
the digits 0-7.
То есть
Ноль (или 0о, или 0О) в начале записи числа указывает на то, что число записано в восьмеричном виде.
Откуда в Вашем javascript-е берутся числа в такой записи?
В Python есть встроенный модуль поддерживающий точные вычисления с рациональными числами:
from fractions import Fraction
print(Fraction(2, 3) + Fraction(5, 7))
Все здорово, если учитывать, что питон по умолчанию использует длинную арифметику.
Мне недавно понадобилось использовать комплексные числа только с рациональными мнимой и действительной частями. Вот что из этого вышло:
>>> from fractions import Fraction
>>> print(Fraction(2, 3) + Fraction(5, 7) * 1j)
(0.6666666666666666+0.7142857142857143j)
>>> print(complex(Fraction(2, 3), Fraction(5, 7)))
(0.6666666666666666+0.7142857142857143j)
Fraction автоматически приводится к float. Как решить проблему?
В C++, например, можно было бы сделать следующим образом:
complex
Нельзя ли нечто подобное сделать в Python?
Я пока, что вижу только одно решение написать свой класс Complex, но надеюсь есть решение проще.
Боюсь, что другого способа действительно нет.
Единственное что, хорошим тоном будет наследоваться от абстрактного класса Complex https://docs.python.org/3.5/library/numbers.html. Это не даст упустить какие-то важные методы и в итоге позволит сделать класс с интерфейсом идентичным оригинальному.
Здравствуй, дали задачу по PHP
Напишите массив с числами от 1 до 30
[1, 2, 3 ....]
и функцию, которая делает следующее
проходит по массиву и каждому числу дописывает фразу "новых комментариев" и эти слова склоняются в соответствии с их числом
и делает в итоге массив
1 новый комментарий
2 новых комментария
и тд
и вывести на экран в
html в элементе
Прошу помочь с примерами решения, в PHP я новичок, теорию изучил не плохо но сижу несколько дней и не дошло пока что использовать в этом примере.
Есть статья относительно множественных чисел. Там собраны алгоримы определения множественного числа для многих стран. Алгоритмы представлены в виде формул. Не нужно изобретать велосипед. Мы же используем формулы в математике.
В данном случае мы берем русский язык: nplurals=3
То есть для русского языка три множественные формы:
1) Когда элемент один. Например: 1 новый комментарий
2) Когда элементов больше двух, но меньше пяти. Например: 3 комментария, 4 комментария
3) Когда элементов больше или равно пяти. Например: 5 новых комментариев, 6 новых комменариев
Теперь перейдем к реализации. Условия привел в более читаемый вид:
$numbers = ['1', '2', '3', '4', '5'];
function plural($number)
{
if ($number % 10 == 1 && $number % 100 != 11) {
return $number . ' новый комментарий';
} else {
if ($number % 10 >= 2 && $number % 10 <= 4 && ($number % 100 < 10 || $number % 100 >= 20)) {
return ($number . ' новых комментария');
} else {
return ($number . ' новых комментариев');
}
}
}
foreach ($numbers as $number) {
echo plural($number);
echo '
';
}
Задачка кажется очень простой, но все равно не выходит.
Дан массив целых чисел, упорядоченный строго по возрастанию.
Дано некоторое число X, нужно менее чем за квадратное количество операций(то есть перебор всех пар) найти такие два любых элемента массива, что их сумма равна X, иначе вывести 0.
Как сделать это меньше, чем за квадратное время?
Подкиньте идею какую-нибудь, ну или сам подход?))
Спасибо=)
Решение за О(n):
Решаем методом "2 указателя"
Храним 2 индекса: первый сначала указывает на нулевой элемент, второй - на последний элемент.
Цикл - пока индексы не будут равны (то есть пока они не укажут на один и тот же элемент. Если такое случилось - значит, искомых элементов в массиве нет).
На каждой итерации цикла сравниваем текущую сумму (сумму элементов, на которые указывают индексы) с искомой. Если сумма меньше - увеличиваем первый индекс, если сумма больше - уменьшаем второй индекс. Если равна - решение найдено.
#include
using namespace std;
int main()
{
int *a; // массив
int n; // количество элементов в массиве
int sum; // необходимая сумма
///
//чтение массива
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> sum;
///
// индексы
int lt = 0; // первый, то есть левый
int rt = n - 1; // второй, то есть правый
while (lt != rt)
{
int cursum = a[lt] + a[rt];
if (cursum < sum)
lt++;
else if (cursum > sum)
rt--;
else // if (cursum == sum)
{
cout << "indexes: " << lt << " " << rt << endl;
cout << "values: " << a[lt] << " " << a[rt] << endl;
return 0;
}
}
cout << "not found" << endl;
return 0;
}
Задача. Даны два числа s и p, при этом s <= p. Требуется найти ближайший после s делитель d числа p, такой что:
s <= d
p mod d = 0
если s != d, то p mod (s,d] != 0 // в дипазоне от s до d нет делителей
Например, для s = 7 и p = 33, d = 11
Придумал два вот таких варианта:
// тупой перебор
int delimeter_1(int s, int p)
{
if(s <= p)
{
int d = s;
while(0 != p % d)
{
++d;
}
return d;
}
return p;
}
// перебор поумнее
int delimeter_2(int s, int p)
{
if(s <= p)
{
int q = p / s;
while(0 != p % q)
{
--q;
}
return p / q;
}
return p;
}
Пояснение. Например для числа 15 построим таблицу:
делители: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
частное : 15 7 5 3 3 2 2 1 1 1 1 1 1 1 1
остаток : 0 1 0 3 0 3 1 7 6 5 4 3 2 1 0
Так вот, в delimeter_1 мы движемся по строке делители, а в delimeter_2 по строке частное - второй вариант получается чуть быстрее.
У меня есть подозрение, что возможно есть более быстрое и элегантное решение, основанное на свойствах чисел, либо вообще без циклов, либо с более короткими циклами. Мне не обязательно готовое решение, может кто-то подскажет где почитать на близкую тему или выскажит интресные мысли и замечания.
Подумав, пришел к выводу, что аналитического неитерационного алгоритма не сущетсвует. Такой алгоритм можно представить в виде некой функции f(q,s) = d, то есть q mod f(q,s) = 0, или в виде уравнения q mod (s + k) = 0, где s + k = d. Как вытащить k мне не известно, перешерстил все и ничего не нашел.
Решая перебором, следует комбинировать оба подхода. Для p/d < d применять первый, для p/d > d второй. Т.е. сначала бежим по делителям, потом по частным. В случае с таблицей по 15 будет от 1 до 4 (по делителю) первый подход, от 3 до 1 (по частным) второй.
Для варианта d = 1000 таблица будет из 1000 столбцов, а итераций от 1 до 31 и обратно от 31 до 1 всего 62 (плюс-минус) максимум.
Дальше учитываем s и оптимизируем. Т.к. для первого подхода мы пройдем все делители от s до sqrt(p) второй раз при проходе по частным эти делители проходить не нужно, второй подход можно сразу начинать с s и до 1.
Получаем простой цикл от 1 до sqrt(p), просто для выявления ближайшего к s делителя порядок не прямой.
В итоге:
int delimeter_3(int s, int p)
{
int i = s;
while(i > 1)
{
if(p % i==0) break;
if(i >= s) i++ else i--;
if(i > sqrt(p)) i = min(s, p / s) - 1;
}
return i >= s ? i
: i ? p / i
: p;
}