Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.
Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.
Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.
| Входные данные | Вывод программы |
| 10 | 9 |
| 25833798135522720 | 4918510377816614 |
| 88888888888888 | 20334926626631 |
Быстрое возведение в степень
Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$
Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.
Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 23 | SSXSXSX |
| 2 | 1 | |
| 3 | 16 | SSSS |
| 4 | 1000000 | SXSXSXSSXSSSSSXSSSXSSSSSS |
| 5 | 2018 | SXSXSXSXSXSSSSXS |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; int main() { long long n, k = 0; cin >> n; int c = 0; while (n > 1) { long long bit = n & 1; n >>= 1; k <<= 1; k |= bit; c += 1; } while (c--) { long long bit = k & 1; k >>= 1; cout << (bit == 0 ? "S" : "SX"); } return 0; } |
Условие задачи можно найти на e-olymp
Код решения — ideone
Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:
1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;
2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];
3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].
Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.
В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.
В первой строке одно целое число – номер цвета заданной бусинки.
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | [latex]10[/latex] | [latex]2[/latex] |
| 2 | [latex]116[/latex] | [latex]3[/latex] |
| 3 | [latex]1[/latex] | [latex]1[/latex] |
| 4 | [latex]454[/latex] | [latex]2[/latex] |
| 5 | [latex]12301230[/latex] | [latex]2[/latex] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <cmath> using namespace std; int main() { int n, m; double k; cin >> n; m = log2(n); k = log2(n); while (m != k){ n = n - (pow(2,m)); m = log2(n); k = log2(n); } cout << m + 1; return 0; } |
Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.
• Задача на e-olymp.
• Решение на сайте ideone.
| n | A | b | Результат |
| 3 | 1 1 11 1 1
1 1 1 |
5 5 5 | 45 45 45 |
| 5 | 1 0 0 0 00 2 0 0 0
0 0 3 0 0 0 0 0 4 0 0 0 0 0 5 |
8 1 8 1 8 | 8 4 72 16 200 |
| 2 | 1 00 1 | 2 2 | 2 2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> using namespace std; int main() { int n; cin >>n; double matr1[n][n]; //Матрица А double matr2[n][n]; // Матрица А^2 double vet1[n]; //Вектор данный по условию (вектор b) double vet2[n]; //Конечный вектор for(int i=0;i<n;i++){ for(int j=0; j<n; j++) // Инициализация матрицы А cin>>matr1[i][j]; } for(int i=0; i<n;i++){ for(int j=0;j<n;j++){ //Возведение матрицы А в квадрат matr2[i][j]=0; for(int p=0;p<n;p++) matr2[i][j]+=(matr1[i][p]*matr1[p][j]); } } for(int i=0; i<n; i++) //Инициализация вектора cin >> vet1[i]; for(int i=0;i<n;i++){ vet2[i]=0; for(int j=0; j<n; j++){ vet2[i]+=matr2[i][j]*vet1[j]; //Умножение матрицы на вектор } } for(int i=0; i<n; i++) cout << vet2[i] << "\t"; //Вывод вектора cout << endl; return 0; } |
Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.
Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.
Ссылка на ideone.com
| Степень | Входная матрица | Результирующая матрица | ||||||||
| 2 |
|
|
||||||||
| 3 |
|
|
Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).
Преимущество этого алгоритма в сравнении с простейшим состоит в том, что простейший алгоритм требует числа умножений, растущего как линейная функция от [latex]n[/latex], а здесь число умножений грубо говоря, пропорционально количеству цифр числа [latex]n[/latex] или двоичному логарифму [latex]n[/latex]. Это преимущество весьма ощутимо при работе с матрицами (из-за трудоемкости каждого умножения), хотя, разумеется, этот алгоритм может быть использован и для вычисления степени любого числа.
Написать программу, реализующую предположенный алгоритм.
Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на временную матрицу матрицу ответ.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <iostream> #include <string> #include <vector> #include <deque> using namespace std; class matrix{ //создаем класс матрицы, в основном для красивого перемножения private: int n,m; int long long **arr; public: matrix(){ n = 1; m = 1; } matrix(int x){ n = x; m = x; arr = new int long long *[n]; for(int i = 0; i < n; i++){ arr[i] = new int long long [m]; } for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ arr[j][k] = 0; } } } matrix(int x, int y){ n = x; m = y; arr = new int long long *[n]; for(int i = 0; i < n; i++){ arr[i] = new int long long [m]; } for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор for(int k = 0; k < this->m; k++){ arr[j][k] = 0; } } } // выше были описанны конструкторы ~matrix(){ for(int i = 0; i < n; i++){ delete arr[i]; } delete arr; }// деструктор void read(){ for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ cin >> arr[j][k]; } } }//функция ввода void write(){ for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ cout << arr[j][k] << " "; } cout << endl; } }// функция вывода void create(int x, int y){ n = x; m = y; arr = new int long long *[n]; for(int i = 0; i < n; i++){ arr[i] = new int long long [m]; } }//функция измененияколичества выделяемой под нас памяти matrix& operator=(const matrix& x){ for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ arr[j][k] = x.arr[j][k]; } } return *this; }// переопределение оператора присваивания для матриц const matrix operator*(const matrix& x){ matrix ans(this->n, this->m); for(int i = 0; i < this->n; i++){ for(int j = 0; j < this->m; j++){ for(int k = 0; k < this->m; k++){ ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j]; } } } return ans; }//переопределение умножения для матриц matrix& operator*=(const matrix& x){ matrix ans(this->n, this->m); for(int i = 0; i < this->n; i++){ for(int j = 0; j < this->m; j++){ for(int k = 0; k < this->m; k++){ ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j]; } } } *this=ans; return *this; }//переопределение присвоить равно matrix& pow(int n){ string s; for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0 s+= to_string((n >> i)&1);; } int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой matrix ans(this->n,this->m); for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0; } } matrix temp(this->n,this->m); temp = *this; for(int j = 0; j <= i; j++){ if(s[j] == '1'){ ans*=temp; } temp*=temp; } *this=ans; return *this; } }; int main() { int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа cin >> n; matrix mas(size); // создаем матрицу mas.read(); mas.pow(n); mas.write(); return 0; } |
Для отправки комментария необходимо войти на сайт.