1. Для запуска программы, код которой был написан на компилируемом языке, на компьютере должен быть установлен компилятор этого языка.
Нет, если программа была откомпилирована на компьютере с процессором, имеющим такую же систему команд и в операционной системе (ОС), формат исполняемых программ которой, совместим с форматом для ОС данной машины.
2. Код программы, написанный на языке, который компилируется в машинный код, достаточно скомпилировать однажды, и потом программу можно будет запустить на любой операционной системе, для которой существует компилятор этого языка.
Да, если операционная система предназначена для процессоров с совместимой системой команд.
3. Для запуска программы, код которой был написан на интерпретируемом языке, на компьютере должен быть установлен интерпретатор этого языка.
Да.
4. Код программы, написанный на языке, который компилируется в байт код виртуальной машины, достаточно скомпилировать однажды, чтобы программу можно было запускать на любой операционной системе, где есть соответствующая виртуальная машина.
Да, именно так переносят между компьютерами так называемые portable приложения, в которых есть как компилируемый, так и интерпретируемый код.
5. Код программы, написанный на интерпретируемом языке, можно без предварительной компиляции запустить на любой операционной системе, где установлен интерпретатор этого языка.
Да, любой интерпретатор сам осуществляет, если это необходимо, компиляцию в байт-код.
6. Скомпилировать программу на C++ для некоторой архитектуры X можно только на компьютере с архитектурой X.
Нет, существуют так называемые кросс-платформенные компиляторы, позволяющие получать выполняемые коды для машин другой архитектуры. Кроме того, язык С++ является многоплатформенным; это позволяет компилировать написанные на нем программы на любой платформе, где имеется нужный компилятор. При написании кода нужно иметь в виду межплатформенные соглашения, например, нельзя использовать в программе обращания к библиотекам конкретной операционной системы.
Дерево Фенвика для массива A можно себе представлять так, как изображено на прикрепленном рисунке. В вершине, помеченной числом i, хранится сумма A[i] и всех элементов массива A с индексами, которые записаны в левом поддереве вершины i. Например, Fenwick[11] = A[8] + A[9] + A[10] + A[11]. Дерево Фенвика устроено так, чтобы в каждой вершине Fenwick[n] хранилась сумма отрезка массива от некоторого F(n) до n, нужно сообразить, чему равно F(n). F(n) получается, если идти по дереву в левые поддеревья, пока не наткнёмся на лист, он помечен чётным числом. Если двоичная запись числа n оканчивается на k единиц, то в F(n) эти k единиц заменены на нули.
Пусть нужно вычислить сумму префикса A[0..n], например, n = 9. Глядя на дерево, можно сообразить, что эта сумма равна (A[0] + A[1] + ... + A[7]) + (A[8] + A[9)) = Fenwick[7] + Fenwick[9]. В такой сумме обязательно есть Fenwick[n]: A[0] + A[1] + ... + A[n] = (A[0] + ... + A[F(n) - 1]) + (A[F(n)] + ... + A[n]) = (A[0] + ... + A[F(n) - 1]) + Fenwick[n]. Сумму в скобках тоже можно представить в виде суммы Fenwick[...].
Обновление значения A[n] приводит к обновлению некоторых Fenwick[k], а именно, Fenwick[n], и затем всех вершин-родителей, для которых текущая вершина является левым потомком. Например, чтобы обновить A[9], придется обновить Fenwick[9] и Fenwick[11]. Посчитано, что если текущая вершина имеет номер k, то следующая имеет номер k | (k + 1), и так далее, пока не кончатся вершины.
Высота дерева O(log n), так что операции нахождения суммы и обновления элементов работают за O(log n).
1. Для запуска программы, код которой был написан на компилируемом языке, на компьютере должен быть установлен компилятор этого языка.
Нет, если программа была откомпилирована на компьютере с процессором, имеющим такую же систему команд и в операционной системе (ОС), формат исполняемых программ которой, совместим с форматом для ОС данной машины.
2. Код программы, написанный на языке, который компилируется в машинный код, достаточно скомпилировать однажды, и потом программу можно будет запустить на любой операционной системе, для которой существует компилятор этого языка.
Да, если операционная система предназначена для процессоров с совместимой системой команд.
3. Для запуска программы, код которой был написан на интерпретируемом языке, на компьютере должен быть установлен интерпретатор этого языка.
Да.
4. Код программы, написанный на языке, который компилируется в байт код виртуальной машины, достаточно скомпилировать однажды, чтобы программу можно было запускать на любой операционной системе, где есть соответствующая виртуальная машина.
Да, именно так переносят между компьютерами так называемые portable приложения, в которых есть как компилируемый, так и интерпретируемый код.
5. Код программы, написанный на интерпретируемом языке, можно без предварительной компиляции запустить на любой операционной системе, где установлен интерпретатор этого языка.
Да, любой интерпретатор сам осуществляет, если это необходимо, компиляцию в байт-код.
6. Скомпилировать программу на C++ для некоторой архитектуры X можно только на компьютере с архитектурой X.
Нет, существуют так называемые кросс-платформенные компиляторы, позволяющие получать выполняемые коды для машин другой архитектуры. Кроме того, язык С++ является многоплатформенным; это позволяет компилировать написанные на нем программы на любой платформе, где имеется нужный компилятор. При написании кода нужно иметь в виду межплатформенные соглашения, например, нельзя использовать в программе обращания к библиотекам конкретной операционной системы.
Дерево Фенвика для массива A можно себе представлять так, как изображено на прикрепленном рисунке. В вершине, помеченной числом i, хранится сумма A[i] и всех элементов массива A с индексами, которые записаны в левом поддереве вершины i. Например, Fenwick[11] = A[8] + A[9] + A[10] + A[11]. Дерево Фенвика устроено так, чтобы в каждой вершине Fenwick[n] хранилась сумма отрезка массива от некоторого F(n) до n, нужно сообразить, чему равно F(n). F(n) получается, если идти по дереву в левые поддеревья, пока не наткнёмся на лист, он помечен чётным числом. Если двоичная запись числа n оканчивается на k единиц, то в F(n) эти k единиц заменены на нули.
Пусть нужно вычислить сумму префикса A[0..n], например, n = 9. Глядя на дерево, можно сообразить, что эта сумма равна (A[0] + A[1] + ... + A[7]) + (A[8] + A[9)) = Fenwick[7] + Fenwick[9]. В такой сумме обязательно есть Fenwick[n]: A[0] + A[1] + ... + A[n] = (A[0] + ... + A[F(n) - 1]) + (A[F(n)] + ... + A[n]) = (A[0] + ... + A[F(n) - 1]) + Fenwick[n]. Сумму в скобках тоже можно представить в виде суммы Fenwick[...].
Обновление значения A[n] приводит к обновлению некоторых Fenwick[k], а именно, Fenwick[n], и затем всех вершин-родителей, для которых текущая вершина является левым потомком. Например, чтобы обновить A[9], придется обновить Fenwick[9] и Fenwick[11]. Посчитано, что если текущая вершина имеет номер k, то следующая имеет номер k | (k + 1), и так далее, пока не кончатся вершины.
Высота дерева O(log n), так что операции нахождения суммы и обновления элементов работают за O(log n).