Страницы

Поиск по вопросам

пятница, 7 декабря 2018 г.

Генератор случайных чисел без повторений C++. Получить диапазон 1..7 в случайном порядке

Сижу, ломаю голову - и все никак не получается. Нужно создать массив из случайных чисел в диапозоне от 1 до 7 и чтобы там не было повторений. Я знаю, что есть много вариантов решения, но я выбрал следующий: при генерации числа заносить его в массив, а при генерации следующего пробегаться по массиву в поисках совпадения. Если найдено, то генерировать заново. Написал код, вроде бы все легко, но в ответе все равно проскальзывают повторения. Подскажите, где косяк?
#include "pch.h" #include #include #include #include #include #include #include #include #include
using namespace std;
int main() { setlocale(LC_ALL, "Russian"); SetConsoleCP(1251); SetConsoleOutputCP(1251);
srand(time(0));
int a[7] = {0,0,0,0,0,0,0}; //создаю массив и заполняю нулями int random; //переменная для случайных чисел
for (int i = 0; i < 7; i++) { //цикл создания случайных чисел random = 1 + rand() % 7; //создание случайного числа for (int j = 0; j < 7; j++) { //цикл проверки массива на совпадение if (random == a[j]) { //условие совпадения while (random == a[j]) { //цикл для создания нового случайного числа, пока оно не будет повторяться random = 1 + rand() % 7; } } else { continue; //если повтора нет, переходим к следующей итерации } } a[i] = random; // присваивание рандомного числа элементу массива }
for (int k = 0; k < 7; k++) { //вывод массива на экран cout << a[k]; }
cout << "Для выхода из консоли нажмите любую клавишу"; _getch(); return 0; }


Ответ

Для такого малого количества просто возьмите массив {1,2,3,4,5,6,7} и случайным образом его перетасуйте (например, с помощью shuffle). Будет быстрее и проще.
А ваша проблема в том, что, проверив число на равенство одному a[j] и откорректировав, вы тут же об этом забываете при проверке на следующее значение j. Т.е. ваш цикл должен выглядеть примерно как
for (int i = 0; i < 7; i++) { for(;;) { bool good = true; random = 1 + rand() % 7; for (int j = 0; j < 7; j++) { if (random == a[j]) { good = false; break; } } if (good) break; } a[i] = random; // присваивание рандомного числа элементу массива }

Скачивание файла через urllib

Подскажите, пожалуйста, как скачать файл средствами python (urllib) доступный по http и положить его рядом со скриптом?


Ответ

urllib -> urlopen - открывает файл по данной ему ссылке для чтения, далее можете его просто считать read(), открыть файл для бинарной записи, и записать в него то что прочитали по http. Пример скачивания эмблемки:
import urllib logo = urllib.urlopen("http://www.google.com/images/srpr/logo3w.png").read() f = open("logo3w.png", "wb") f.write(logo) f.close()
Также есть urllib.urlretrieve(url, [filname,[...]]) - по моему его предназначение именно для скачивания.
import urllib destination = 'logo3w.png' url = 'http://www.google.com/images/srpr/logo3w.png' urllib.urlretrieve(url, destination)

Явные отличия CMP от TEST

Я начал изучать устройство одной программы недавно, целиком написанной на ассемблере (т.е никакие трансляторы в машинный не применялись, как в языках высокого уровня). Так вот, в ней я очень часто встречаю конструкции вида TEST AL, AL ; TEST EAX, EAX и т.д.
Вот вопрос: почему применяется TEST, а не CMP? Да и какой смысл сравниваться с самим собой? Насколько я знаю, TEST использует логическое "И" (AND). Проясните, пожалуйста, в этих деталях я не особо просвещён.


Ответ

Команды вида test reg, reg используется для сравнения значения регистра с нулем. После этой операции флаги нуля, знака и чётности либо устанавливаются, либо сбрасываются. Почему не cmp reg, 0? Потому что в скомпилированном виде test reg, reg на целый байт короче, ну и по скорости наверное разница есть.
test эквивалентен побитовому and, за исключением того, что модифицируются только флаги, но не операнды. Обычно это нужно, чтобы узнать, установлены ли определенные биты в регистре.
А cmp эквивалентен обыкновенному вычитанию, но аналогично модифицирует флаги, не изменяя операнды.

Присваивание символа const char *

Добрый день, хочу расставить точки над «i» для себя.
const char *v = "123d"; const char *c = "123"; c[2] = '5'; // Так нельзя c = v; c = "asdfas";
Вопрос в следующем. Почему, когда мы const char * присваиваем строку, он присваивает, а символ — нет? Может, где-то для const char * перегружен оператор присваивания, и он ему присваивает новый адрес? А при присваивании литерала мы пытаемся записать по тому же адресу?


Ответ

Вопрос в следующем. Почему, когда мы const char * присваиваем строку, он присваивает, а символ — нет?
Нужно различать константный указатель и указатель на константу.
1) Указатель на константу: нельзя менять содержимое объекта, на который указывает указатель, но можно менять содержимое самого указателя (указатель — это переменная, содержащая адрес другой переменной).
char array[] = "string"; const char * с = array; // Указатель на объект, который нельзя менять c[1] = 'a'; // Нельзя, т. к. меняется содержимое указываемого объекта с = "345"; // Можно, т. к. меняется значение самого указателя
2) Константный указатель: можно менять содержимое объекта, но нельзя менять значение самого указателя. Проще говоря, указатель нельзя переназначить на другой объект, но сам указатель поменять можно.
char array[] = "string"; char * const с = array; c[1] = 'a'; // можно с = "345"; // нельзя
3) Константный указатель на константу: совокупность первых двух.
const char * const с = "123";

Поиск повторяющихся строк

Привет. Возник вопрос: Есть файл 1 ~ 2GB и есть файл 2 ~ 1MB Вопрос - как наиболее быстро подсчитать кол-во вхождений строк из файла2 в файле1? К примеру файл1: Тест корова большая Флагман большая корова Трубадур золотистый Флагманский телефон N90 Логическое оформление Тест корова Бла бла стар Файл2: Трубадур Тест корова телефон Должно получиться: Трубадур 1 Тест корова 2 телефон 1 Файл 1 много больше файл2.


Ответ

Эффективным методом поиска нескольких подстрок одновременно в большом тексте является алгоритм Ахо-Корасика. Оригинальный fgrep (grep -F) использует этот алгоритм. GNU grep в этом случае использует Commentz-Walter алгоритм (объединение Ахо-Корасика и алгоритма поиска строки Бойера—Мура). ripgrep (rg) иногда работает быстрее GNU grep, используя SIMD алгоритм, называемый Teddy -- см. ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}
Чтобы подсчитать найденные строки, можно использовать sort | uniq -c команду, предложенную @BOPOH в комментарии к вопросу. Ещё можно использовать словарь вместо сортировки:
#!/bin/sh grep -Fof file2 file1 | perl -lne '$seen{$_}++ }{ while (my ($k,$v)=each %seen){print "$k $v"}'
Измерения могут показать, какая из команд (sort+uniq или perl) быстрее в данном случае.
Для сравнения можно посмотреть, сколько займёт Питон-скрипт без использования дополнительных пакетов (например, esm), которые реализуют Ахо-Корасик-подобные алгоритмы:
#!/usr/bin/env python import re import sys from collections import Counter
def main(): # load substrings from file2 with open('file2', 'rb') as file2: substrings = {line.strip() for line in file2} # unique lines substrings = filter(None, substrings) # filter blank lines substrings = sorted(substrings, key=len, reverse=True) # longest first pattern = b"|".join(map(re.escape, substrings)) find_substrings = re.compile(pattern).findall
# count substrings in file1 counter = Counter() counter_update = counter.update # cache the lookup (for CPython) with open('file1', 'rb') as file1: for line in file1: counter_update(find_substrings(line))
# write substrings frequencies write = getattr(sys.stdout, 'buffer', sys.stdout).write for substring, count in counter.most_common(): # most common first write(substring) write(b' ') write(str(count).encode()) write(b'
')
main()
Результат
Тест корова 2 телефон 1 Трубадур 1
Вот ещё вариант для сравнения, где строки в файле ищутся с помощью регулярного выражения и mmap
#!/usr/bin/env python3 import re import sys from collections import Counter from mmap import ACCESS_READ, mmap from operator import methodcaller
def generate_tokens(filename, pattern): with open(filename) as f, mmap(f.fileno(), 0, access=ACCESS_READ) as mm: yield from re.finditer(pattern, mm)
def main(): # load substrings from file2 with open('file2', 'rb') as file2: substrings = {line.strip() for line in file2} # unique lines substrings = filter(None, substrings) # filter blank lines substrings = sorted(substrings, key=len, reverse=True) # longest first pattern = b"|".join(map(re.escape, substrings))
# count substrings in file1 file1_substrings = generate_tokens('file1', pattern) counter = Counter(map(methodcaller('group'), file1_substrings))
# write substrings frequencies write = getattr(sys.stdout, 'buffer', sys.stdout).write for substring, count in counter.most_common(): # most common first write(substring) write(b' ') write(str(count).encode()) write(b'
')
main()
Работает на Windows, *nix. Код для Питон 3, но его можно легко адаптировать для Питон 2, если необходимо.

четверг, 6 декабря 2018 г.

Почему нельзя запустить android приложение на Linux?

Здравствуйте! Почти все приложения для Android написаны на Java. И тем не менее их нельзя запустить на компьютере. Почему? А если перекомпилировать? В чем разница между Java на Android и Linux? Можно их запустить на компьютере?


Ответ

Во первых Андроид это операционная система и работает на виртуальной машине по жавой. Хоть и сделана на база линукса они разные, разные библеотеки, дрова и тд. Тем более приложение компилируется на архитектуру процессоров ARM. Но запустить на компе возможно с помощью эмулятора, па пример Genymotion.

Вернуть md5 к исходному значению на С

Подскажите какой-нибудь декриптор или что-нибудь в этом роде на Си для md5. Нужно сделать так, чтобы шифровка md5 превращалась в то, что было до шифрования. Возможно ли такое в принципе, и если нет, то почему?


Ответ

MD5 - это не "шифрование", это хэш-функция. Основное требование к криптографическим хэш-функциям - необратимость.
Если бы хэши были обратимы, то архиваторы и прочие алгоритмы сжатия стали бы не нужны. Например, я посчитал хэш от терабайтного файла. Получил 79a2520f22b9e1526ff93176029603b8. Вы считаете что можно эту строчку расшифровать обратно в тот же терабайт информации?
Максимум, что можно сделать для MD5 - найти коллизию (второй прообраз) - строчку, для которой MD5 выдаст такое же значение. Это можно сделать или по готовым словарям (если есть подозрение что строчка - это пароль вида 12345), или с использованием радужных таблиц.
Но никакой гарантии что вы получите при этом именно оригинальную строку нет. Точнее, вы с некоторой вероятностью получите оригинальную строку, если она была короткой. Но вы точно получите неоригинальную строку, а просто коллизию, если оригинал был достаточно длинным.
Если поиска коллизии для вас достаточно - поищите готовую опен-сорс реализацию работы с радужными таблицами, например MD5Rainbow