On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 27.01.13 16:44. Заголовок: Cracking The Coding Interview. 150 Programming Interview. Questions and Solutions.


Встретил в книжном магазине такую книгу: "150 тестовых заданий. Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию" Г. Лакмана Макдоуэлла. Соответствующее английское название книги - "Cracking The Coding Interview. 150 Programming Interview. Questions and Solutions" 5-th Edition by Gayle Laakmann MacDowell.

Я пролистал книгу, но пока еще не решил, стоит ли ее брать.

Во-первых, я никогда не делаю никаких тестовых заданий. И вам рекомендую поступать точно также. Вам никто отдолжение не делает. С вами должны договариваться, как со специалистом, а не устраивать "конкурс красоты среди готовых на все барышень".
Во-вторых, я убедился, что я просто бы не прошел тестирование, так как уже для самого простого теста, как я считаю, мой ответ разошелся с тем, что предлагается в качестве решения в книге.

Это простое тестовое задание размещено в главе 12 "Тестирование". Предлагается в предложенном ниже коде на языке C найти ошибку или ошибки, если таковые имеются. Вот этот код:

1. unsigned int i;
2. for ( i = 100; i>= 0; --i )
3. printf( "%d\n", i );

В разделе решения для этого кода утверждается, что в коде имеются две ошибки. Первая ошибка связана с тем, что в цикле используется переменная типа unsigned int, а объекты этого типа принимают неотрицательные значения.Поэтому условие цикла i >= 0, будет истинно для любого значения переменной, а, следовательно, цикл будет бесконечным.

С этим, естественно, никто спорить не будет. Далее предлагается такое решение: заменить условие цикла i >= 0 на i > 0, и тогда будут распечатаны числа от 100 до 1 включительно в цикле. А если вам нужно напечатать еще и 0, то придется после цикла вставить дополнительное предложение с printf.

Вторая ошибка заключается в том, что следует использовать символ форматирования %u вместо %d, поскольку выводятся целые значения без знака.

Ни с одним из данных утверждений в решении, представленном для этого примера кода, я не согласен. Начну со второго утверждения. На самом деле использование символа форматирования %d для данного примера не является ошибкой. Область значений, соответствующая отрезку [0, 100] является одинаковой областью допустимых значений для знаковых и беззнаковых целочисленных значений. Поэтому вывод будет корректным. Никакой ошибки в этом нет.

Согласно разделу 6.2.6.2 Integer types стандарта С:

5 The values of any padding bits are unspecified.54) A valid (non-trap) object representation of a signed integer type where the sign bit is zero is a valid object representation of the corresponding unsigned type, and shall represent the same value.

А также разрешается использовать unsigned тип там, где ожидается signed тип при условии, что (6.5.2.2 Function calls, #6)

— one promoted type is a signed integer type, the other promoted type is the corresponding unsigned integer type, and the value is representable in both types;

Я укажу далее, когда использование символа форматирования %d, действительно является ошибкой. Другое дело, что это противоречит культуре программирования, но тем не менее ошибкой не является.

Теперь перейдем к первому утверждению решения, предлагаемого в книге. Очевидно, что автор исходного кода ставил цель вывести числа от 100 до 0 включительно в одном предложении цикла. Разбиение этого кода на цикл и еще отдельное предложение вне цикла не соответствует исходной целе. Более того логически единая задача теперь разбивается, фактически, на две самостоятельные задачи, которые семантически не связаны между собой и выглядят, как два независимых участка кода.

Так, как сделать так, чтобы распечатать числа от 100 до 0 включительно с помощью одного цикла без дополнительных предложений после цикла? Сделать на самом деле это просто. Но сначала я сделаю примечание, что исходный пример скорей всего написан на C89, который не позволял определять локальные переменные внутри цикла. В своих примерах кода я буду предполагать, что используется C99.

Итак, чтобы распечатать числа от 100 до 0 включительно, можно сделать так:

1. for ( unsigned int i = 101; i > 0; --i )
2. printf( "%d\n", i - 1 );

Как можно видеть, все делается с помощью одного цикла. При этом я сознательно оставил символ форматирования %d в соответствии с тем объяснением, которое я давал выше.

Но чем плох этот код? Он зависит от конкретного "магического значения". Очевидно, что такой код следует избегать. Поэтому далее вместо числа 100 я буду использовать переменную n, которая будет хранить некоторое начальное значение для цикла.

В этом случае уже нельзя использовать предыдущий пример, просто заменив число 100 на переменную n. Действительно, если мы перепишем предыдущий код следующим образом

1. for ( unsigned int i = n + 1; i > 0; --i )
2. printf( "%d\n", i - 1 );

то при n = UINT_MAX, мы получим, что n + 1 будет равно 0, а, следовательно цикл ни разу не выполнится! Более того именно для такого кода использования символа форматирования %d является ошибкой, так как в этом случае области допустимых значений для знакового и беззнакового целых чисел не совпадают! А потому мы должны использовать символ форматирования %u.

Так что же делать? Давайте зададим себе такой вопрос, если цикл for каким-то образом написан корректно, то существует ли такое неотрицательное целое число, для которого цикл ни разу не выполнился бы? Очевидно, что такого числа нет, то есть по крайней мере одна итерация цикла должна быть выполнена, ведь 0 мы также должны вывести на консоль! Что из этого следует? Напрашивается использование цикла do-while. Действительно, при использовании do-while, код будет корректным и решать поставленную задачу без всяких проблем:

1. unsigned int i = n;
2. do { printf( "%u\n", i ); } while ( i-- );

Опять-таки, обратите внимание, что никаких дополнительных предложений после цикла не требуется, то есть замысел автора исходного кода реализован полностью.

А как все-таки сделать то же самое, но с использованием цикла for?
Для этой конкретной задачи, когда тело цикла состоит всего лишь из вызова одной функции, сделать это очень просто!

1. for ( unsigned int i = n; printf( "%u\n", i ) > 0 && i != 0; --i );

Фактически, цикл do-while реализован с помощью цикла for с применением простого трюка по размещению тела цикла внутри самого цикла до проверки основного условия.

А что делать, если тело цикла не такое простое, как в исходном примере, а может состоять из многих предложений, которые будет невозможно поместить внутрь самого цикла for?

Из этой ситуации также есть достаточно простой выход, но который требует остроты ума.
Вот соответствующий код. Я его не буду комментировать, чтобы вы самостоятельно убедились, что он работает корректно и выводит на консоль любой диапазон целых чисел без знака.

1. for ( unsigned int i = n, j = n; !( i == 0 && j == -1u ); --j )
2. printf( "%u\n", i = j );

Я надеюсь, что я вас убедил, что никогда, повторяю, никогда не унижайтесь ни перед одной фирмой и не делайте никаких тестовых заданий. Они же не собираются делать ваши тестовые задания, не так ли? А они берут вас на работу не из милосердия к вам, а чтобы эксплуатировать ваши знания и квалификацию.

Им нужны ваши знания и квалификация? Тогда пусть с вами договариваются!



Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 14 [только новые]





ссылка на сообщение  Отправлено: 25.08.14 04:44. Заголовок: Вы считаете, что эти..


Вы считаете, что эти шедевры:

 цитата:
1. for ( unsigned int i = n; printf( "%u\n", i ) > 0 && i != 0; --i );



 цитата:
1. for ( unsigned int i = n, j = n; !( i == 0 && j == -1u ); --j )
2. printf( "%u\n", i = j );


превышают по качеству исправленный код авторов книги?

 цитата:
1. unsigned int i;
2. for ( i = 100; i> 0; --i )
3. printf("%d\n", i );
4. printf("0\n");



Сыроежка пишет:

 цитата:
Я надеюсь, что я вас убедил, что никогда, повторяю, никогда не унижайтесь ни перед одной фирмой и не делайте никаких тестовых заданий.


Более того, никогда не унижайтесь и не проходите никакие собеседования. А лучше вообще карьеру программиста завершить, и как можно быстрее.


Спасибо: 0 
Цитата Ответить



ссылка на сообщение  Отправлено: 25.08.14 07:48. Заголовок: В моем описании впол..


В моем описании вполне ясно указано, как следует написать в одном цикле вывод произвольной последовательности неотрицательных чисел, включая 0:

 
1. unsigned int i = n;
2. do { printf( "%u\n", i ); } while ( i-- );


Решение автора не удовлетворяет поставленному условию. Вместо того, чтобы правильно подобрать конструкцию цикла такую, как do-while,, он вынужден разбивать свой код на два отдельных участка кода, один - в цикле и другой - вне цикла, дублируя при этом код и логически разрывая единую операцию.

Но, похоже, вы предпочли этого не заметить.

Далее я просто рассматриваю в тексте искусственные начальные условия к задаче: как все-таки можно в одном цикле for выполнить поставленную задачу, и можно ли это сделать вообще. Для решения этой задачи следует проявить некоторую смекалку и изобретательность, то есть необходимо нешаблонно мыслить. Нешаблонно мыслить - это одно из креативных качеств программиста. Кстати сказать, попробуйте сами выполнить эту задачу и посмотрите, что у вас получится.:)

Что касается вашего совета завершить карьеру программиста, то мне представляется он неуместным. Например, у меня полно творческих планов по внесению предложений по изменению и развитию стандарта языка C++. Наверное вы уже в курсе дела, что не так давно по моему предложению был исправлен дефект стандарта относительно класса std::basic_string. Этот дефект существовал более 10 лет, и никто кроме меня на него не обращал внимание.

Я - самый активный участник от России (фактически, единственный, от России за исключением некоего Михаила Семенова, но я не знаю, проживет ли он в России или нет) по обсуждению стандарта языка C++ и его развитию в соответствующих группах форумов, специально созданных для этих целей Комитетом по стандартизации. У меня имеется в запасе с десяток предложений по включению их в стандарт языка C++.
К сожалению, если я не ошибаюсь, вас там я не встречал. Или вы находитесь только в самом начале пути карьеры программиста?

Также я - единственный от России, входящий в топ 20-отвечающих на форуме www.stackoverflow.com в разделах C++ и C. В этом списке я вас тоже почему-то не встречал. У меня там золотые знаки отличия (gold badges) по C и C++.

Я это к тому написал, чтобы показать, что ваши личные впечатления обо мне расходятся с реальными фактами. Есть субъективные оценки, а есть вполне объективные критерии, которые существуют независимо от ваших личных симпатий или антипатий. Именно эти критерии и следует принимать во внимание при подборе специалистов, а не устраивать конкурс на лучшее и красочнее написанное резюме.:)




Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 09.09.14 11:51. Заголовок: Как показала реплика..


Как показала реплика Анонимус некоторые программисты страдают косностью мышления. Поэтому я решил в этой теме показать некоторые примеры необычных подходов к написанию циклов, которые на первый взгляд выглядят вычурными, но при более пристальном рассмотрении заслуживают "место под солнцем".

Такие примеры я буду черпать из вопросов, появившихся на форуме www.stackoverflow.com и своих ответов на них.

Вот первый такой пример необычного цикла.

Очень часто требуется выводить на консоль числовые массивы в соответствии с определенным форматом. Например, представим, что нужно вывести на консоль целочисленный массив, чередуя его элементы через запятую:
 
0, 5, 9, 2, 0, 3, 8, 9, 6, 4

Чтобы можно было опробовать предлагаемые решения, желательно написать тестовую программу. Для этого сформулируем простое задание, в котором будет присутствовать данное требование вывода целочисленного массива на консоль в соответствии с указанным форматом.

Пусть требуется задать с консоли произвольный размер целочисленного массива, создать соответствующий массив, ввести в элементы случайно выбранные неотрицательные значение, которые не превосходят по величине значение размера массива и вывести эти значения на консоль, как показано выше.

Такое типичное задание для начинающих программистов.

Проще такую программу писать на языке C, где разрешены массивы переменной длины (Variable Length Arrays - VLA).

Итак, допустив, что массив с именем a уже создан и заполнен значениями. Как можно написать цикл, который выводит его элементы в указанном формате?

Имеется несколько подходов. Первый из них состоит в том, чтобы после каждого выводимого элемента в цикле for вставлять запятую за исключением последнего элемента. Для этого нужно при каждой итерации цикла проверять, не является ли выводимый элемент последним в массиве. Вот как может выглядеть соответствующая программа:
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main( void )
{
size_t n = 0;

printf( "Enter the number of elements in the array (greater than 0): " );
scanf( "%zu", &n );

if ( n == 0 ) exit( 1 );

int a[n];

srand( ( unsigned int )time( NULL ) );

size_t i;

for ( i = 0; i < n; i++ ) a[ i ] = rand() % n;

for ( i = 0; i < n; i++ )
{
printf( "%d", a[ i ] );
if ( i != n - 1 ) printf( ", ");
}

return 0;
}

Эта программа выводит на консоль элементы массива в соответствии с требованием к выводу. Однако такой подход обладает одним недостатком: помимо вывода самого значения элемента массива на консоль он постоянно производит сравнение управляющей переменной i с граничным значением n - 1. Хотя такое сравнение требуется в принципе только один раз при выводе последнего элемента массива.

Как можно исправить цикл, чтобы не делать этих излишних многочисленных сравнений?

Можно сначала вывести первый элемент массива, а затем если в массиве существуют еще элементы, то перед выводом каждого из них вставлять вывод запятой. Вот как будет выглядеть соответствующая программа:
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main( void )
{
size_t n = 0;

printf( "Enter the number of elements in the array (greater than 0): " );
scanf( "%zu", &n );

if ( n == 0 ) exit( 1 );

int a[n];

srand( ( unsigned int )time( NULL ) );

size_t i;

for ( i = 0; i < n; i++ ) a[ i ] = rand() % n;

i = 0;

printf( "%d", a[ i ] );

while ( ++i < n )
{
printf( ", %d", a[ i ] );
}

return 0;
}

Ну и у этого подхода есть свой недостаток. Логически единый цикл разбивается на две части. Сначала выводится на консоль вне цикла первый элемент массива, а затем с помощью цикла - остальные элементы массива.

Возникает вопрос: а можно ли написать такой цикл, который не будет иметь указанных недостатков?

Да, можно! Но для этого нужно отойди от шаблонных стереотипов в написании циклов. Сделать это можно следующим образом:
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main( void )
{
size_t n = 0;

printf( "Enter the number of elements in the array (greater than 0): " );
scanf( "%zu", &n );

if ( n == 0 ) exit( 1 );

int a[n];

srand( ( unsigned int )time( NULL ) );

size_t i;

for ( i = 0; i < n; i++ ) a[ i ] = rand() % n;

i = 0;

do
{
printf( "%d", a[ i ] );
} while ( ++i < n && printf( ", ") > 0 );

return 0;
}

В используемом в этой программе подходе нет ни избыточного сравнения в цикле, ни отдельного вывода первого элемента на консоль вне цикла.

Можно конечно возразить, что лучше писать программы менее эффектные, но более читаемые. Но на мой взгляд приведенный пример является не менее читаемым, чем показанные два примера выше. В этой программе (условно говоря) предложение printf( ", ") > 0 выполняется только тогда, когда i < n. в ней нет избыточного сравнения, а все элементы массива выводятся на консоль в одном цикле.

Так что такой подход к написанию цикла имеет право на существование.

Интересно отметить, что в результате в примерах были использованы все три типа циклов, существующих в языке C: for, while и do-while.

Этот пример взят из моего ответа на www.stackoverflow.com на следующий вопрос

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 09.09.14 22:58. Заголовок: Следующий вопрос мож..


Следующий вопрос может показаться абсурдным. Можно ли разместить одно предложение for внутри другого управляющего предложения for в его третьей части, как, например, показано ниже,

 
for ( size_t i = 1;
i <= n;
( for ( size_t j = 1; j <= i; j++ ) std::cout << '*' ), i++ )
{
std::cout << std::endl;
}


Конечно сделать это нельзя ни в C, ни в C++. Оба языка в третьей части предложения for допускают только выражение.

Более того сразу же возникает вопрос: а зачем это нужно делать, если можно второй цикл просто разместить в теле первого цикла. Например
 
for ( size_t i = 1; i <= n; i++ )
{
for ( size_t j = 1; j <= i; j++ ) std::cout << '*';
std::cout << std::endl;
}


Так что новаторское предложение по размещению одного управляющего предложения for
внутри другого управляющего предложения for представляется бессмысленным.

Однако если внимательно присмотреться к предложенной конструкции и ее замене на существующие конструкции, то окажется, что в общем случае они не эквивалентны!

Действительно, представим, что вам надо в конце одного внешнего цикла обязательно безусловно выполнить некоторый другой цикл. Однако если внешний цикл содержит предложения continue, то возникают определенные трудности. Либо вам придется дублировать внутренний цикл перед каждым предложением continue, либо использовать давно забракованное предложение goto. которое будет передавать управление на конец внешнего цикла, где перед закрывающейся фигурной скобкой будет размещен внутренний цикл.

Очевидно, что оба решения не удовлетворительны.

Так как поместить одно предложение for внутрь другого предложения for?

Сделать это можно с помощью лямбда-выражения!
 
for ( size_t i = 1;
i <= n;
[]( int i )
{
for ( int j = 1; j <= i; j++, ( std::cout << '*' ) );
}( i ), i++ )
{
std::cout << std::endl;
}


Ниже приведена демонстрационная программа
 
#include <iostream>

int main()
{
while ( true )
{
std::cout << "Enter a non-negative number (0-exit): ";

size_t n = 0;
std::cin >> n;

if ( n == 0 ) break;

for ( size_t i = 1;
i <= n;
[]( int i )
{
for ( int j = 1; j <= i; j++, ( std::cout << '*' ) );
}( i ), i++ )
{
std::cout << std::endl;
}

}

return 0;
}



Фактически, эта конструкция эквивалентна той, что была использована в исходном вопросе.

Конечно такой код нелегко читать, а потому лямбда выражение лучше определить отдельно от цикла.
 
#include <iostream>

int main()
{
while ( true )
{
std::cout << "Enter a non-negative number (0-exit): ";

int n = 0;
std::cin >> n;

if ( n == 0 ) break;

auto inner_loop = []( int i )
{
for ( int j = 1; j <= i; j++, ( std::cout << '*' ) );
};


for ( int i = 1; i <= n; inner_loop( i++ ) )
{
std::cout << std::endl;
}
}

return 0;
}


Как видите, все-таки можно разместить одно предложение for внутри другого предложения for!

Ознакомиться с исходным вопросом, заданным на сайте www.stackoverflow.com, можно по следующей ссылке

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 15.03.15 12:12. Заголовок: Для этого сообщения ..


Для этого сообщения причиной его появления послужил следующий вопрос о бесконечном цикле на stackoverflow.

Суть вопроса такова: почему данный цикл является бесконечным
 
for ( int i = 0; i <= 32767; i++ )
{

printf( "%d\n", i );
}


Ответ на этот вопрос очевиден. В той среде, где запускался этот цикл, размер объектов типа int составляет два байта и, соответственно, INT_MAX как раз равно значению 32767. Поэтому когда переменная i достигает этого значения, то после вычисления выражения i++ устанавливается знаковый бит во внутреннем представлении i, и она принимает значение INT_MIN. Очевидно, что INT_MIN меньше чем INT_MAX, и цикл продолжает свою работу. Этот процесс будет бесконечным, пока программа не будет прервана.

Этот вопрос интересен не столько объяснением, почему цикл является бесконечным, сколько тем, что он порождает другой вопрос: а как написать данный цикл, который выводит все значения переменной типа int от 0 до INT_MAX включительно?

Конечно можно было бы разбить этот цикл на две части: в самом цикле печатать все значения от 0 до INT_MAX - 1, а затем уже вне цикла напечатать отдельно переменную i для значения INT_MAX. Но этот, казалось бы, простой и напрашивающийся подход на самом деле будет выглядеть вычурным, если верхнее значение диапазона задается некоторой переменной. Например,
 
int n = SOME_VALUE;

for ( int i = 0; i < n; i++ )
{

printf( "%d\n", i );
}

printf( "%d\n", n );

Этот код вызывает вопросы. Например, составляют ли единое целое предложение с printf после цикла и сам цикл или нет? Например, если по какой-то причине нужно убрать цикл, можете ли вы, глядя на код, однозначно ответить, что нужно также удалить и предложение после цикла, или цикл и это предложение между собой не связаны? То есть, как видно, форма выражения идеи - отдельный цикл и предложение после цикла - не соответствует содержанию идеи вывода всех значений из некоторого диапазона, так как теперь исходный диапазон, фактически разбивается на два поддиапазона.

Спросите сами себя, действительно ли вы в своих программах всегда заменяете цикл
 
int n = SOME_VALUE;

for ( int i = 0; i <= n; i++ )
{

printf( "%d\n", i );
}

на цикл
 
int n = SOME_VALUE;

for ( int i = 0; i < n; i++ )
{

printf( "%d\n", i );
}

printf( "%d\n", n );


Только будьте искренными сами с собой!
Я уверен, что в большинстве случаев программисты так и пишут в своих программах
 
int n = SOME_VALUE;

for ( int i = 0; i <= n; i++ )
{

printf( "%d\n", i );
}

либо даже не задумываясь, что переменная n может иметь значение INT_MAX, либо считая, что этого не может быть никогда.

Это аналогично проблеме 2000 года. До 2000 года программисты тоже не задумывались, что 2000 год может наступить ранее, чем они думают, еще при их жизни.

Так как все-таки в одном цикле вывести все значения целочисленной знаковой переменной из диапазона 0 - INT_MAX включительно?

Сделать это можно, введя еще одну управляющую переменную цикла, как показано ниже. Только в этом цикле я поменял тип переменной i с int на signed char, чтобы вывод на консоль не был бы слишком длинным.

Вот программа., демонстрирующая этот подход.
 
#include <stdio.h>
#include <limits.h>

int main(void)
{
for ( signed char i = 0, j = 0; i <= SCHAR_MAX && j != SCHAR_MAX; j = i++ )
{
printf( "%d ", ( int )i );
}

return 0;
}

Как можно убедиться, цикл программы не является бесконечным, и вывод на консоль будет следующим:
 
0 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




Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 27.07.15 14:48. Заголовок: Вот пример еще одног..


Вот пример еще одного необычного цикла.

Так как ранее я нигде не встречал такую реализацию цикла, и, похоже, я - первый, кто придумал этот цикл, то назову его циклом Сыроежки.

Но, сначала опишу задание, которое послужило причиной для изобретения этого цикла.

Допустим, вам надо в цикле вычислять некоторое выражение, которое последовательно зависит от следующих целочисленных значений: 0, -1, 1, -2, 2, -3, 3, ..., -( N - 1), ( N - 1), То есть чередуются отрицательные и положительные значения каждого индекса за исключением 0.

Например, это может быть вызов некоторой функции, аргумент который вычисляется на основе данных чисел, или любое иное выражение. Причем само это выражение или выражение, которое вычисляет указанную целочисленную последовательность, должно присутствовать в теле цикла в единственном экземпляре.

Как написать такой цикл,?

Конечно решений существует много, но цикл Сыроежки в любом случае выделяется своей оригинальностью.

Вот этот цикл Сыроежки, представленный в следующей демонстрационной программе:
 
#include <iostream>

int main()
{
int N = 10;
for ( int i = 0, j = 0; i < N; i += j ^= 1 )
{
std::cout << ( j == 0 ? i : -i ) << std::endl;
}
}

Вывод на консоль будет таким, как то требуется в задании:
 
0
-1
1
-2
2
-3
3
-4
4
-5
5
-6
6
-7
7
-8
8
-9
9

Мне еще не приходилось писать такое выражение в цикле, как это i += j ^= 1. И нигде ранее я такое выражение в циклах не встречал.

Это сообщение написано на основе вопроса и моего ответа на stackoverflow



Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 28.10.15 20:50. Заголовок: Порой даже очень про..


Порой даже очень простые задания на применение циклов могут вызвать серьезные затруднения у программистов.

Вот одно из таких заданий.

Допустим у вас есть двумерный массив a[M][N]. Требуется его вывести на консоль в "шахматном" порядке для, условно говоря, элементов, расположенных в "белых" клетках.

Что это означает?

Представим, что массив имеет следующие значения своих элементов
 
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Тогда вывод на консоль элементов массива, расположенных в "белых" клетках должен выглядеть следующим образом
 
1 3
6 8
9 11
14 16

Надеюсь, порядок вывода элементов массива понятен. Из первой строки на консоль выводятся элементы с четными номерами позиций в строке (отсчет идет от 0), из второй строки - с нечетными номерами, затем опять - четными номерами и т.д.

Как видите, очень простое задание. Проще будет задание, разве что лишь, вывести весь массив целиком на консоль без каких-либо изысков.

Попробуйте для начала сами выполнить это задание.

Простое? Не спешите! вот какие решения могут быть представлены программистами.
Например,
for ( size_t i = 0; i < M; i += 2 ) 
{
for ( size_t j = 0; j < N; j += 2 )
{
std::cout << a[ i ][ j ] << " ";
}
std::cout << std::endl;
for ( size_t j = 1; j < N; i += 2 )
{
std::cout << a[i + 1][ j ] << " ";
}
std::cout << std::endl;
}

Если вы запустите этот цикл на выполнение, то вы получите как раз тот результат, который показан выше.
Просто? Увы, этот простой код содержит баг!

Вы его уже видите?

Дело в том, что этот цикл будет работать только при условии, что число строк в массиве - четное число. Если же число строк в массиве нечетное, то во втором внутреннем цикле будет предпринята попытка обратиться к несуществующей строке массива!

Вот другое решение, которое может быть предложено программистом.
for ( size_t i = 0; i < M; i++ ) 
{
for ( size_t j = 0; j < N; j++ )
{
if ( ( i + j ) % 2 == 0 ) std::cout << a[ i ][ j ];
}
std::cout << std::endl;
}

Это решение естественно лучше предыдущего, так как, по крайней мере, не содержит баг. Оно построено на том принципе, что "белые" клетки соответствуют элементам массива, для которых сумма номера строки и номера позиции элемента в строке - четное число.

Но у этого решения есть один, правда, несущественный недостаток: во внутреннем цикле при каждой итерации выполняется операция сложения индексов, взятие остатка от деления их на 2 с последующим сравнением с 0. Хотелось бы это сделать проще, не так ли?

Кстати сказать, а каково ваше собственное решение? Вы уже придумали его?

На самом деле можно написать циклы так, что вообще можно обойтись без каких-либо дополнительных операций в теле циклов, кроме вывода очередного элемента массива на консоль.

Вот такое простое и изящное решение:
 
for ( size_t i = 0; i < M; i++ )
{
for ( size_t j = i % 2; j < N; j += 2 ) std::cout << a[ i ][ j ] << ' ';
std::cout << std::endl;
}

Ниже представлена демонстрационная программа, которая наглядно показывает работу этих циклов.

 
#include <iostream>
#include <iomanip>

int main()
{
const size_t M = 4;
const size_t N = 4;
int a[M][N] =
{
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 }
};

for ( size_t i = 0; i < M; i++ )
{
for ( size_t j = i % 2; j < N; j += 2 ) std::cout << a[ i ] [ j ] << ' ';
std::cout << std::endl;
}
}


Вывож на консоль, как и ожидалось будет выглядеть
 
1 3
6 8
9 11
14 16

Все, что требовалось, чтобы получить нужный результат, это инициализировать управляющую переменную второго цикла следующим образом:
 
size_t j = i % 2;

Все Работа выполнена!

Ради интереса предложите своим знакомым программистам, например, коллегам по работе, выполнить данное задание и посмотрите, какие ими будут представлены решения.

Можете в этой теме поместить их решения и не обязательно только корректные решения. Интересно вообще, какие могут быть решения программистов этого простого задания.

Это сообщение я написал на основе вопроса на Stackoverflow , где вы можете ознакомиться с теми решениями, которые я здесь описал.

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 08.12.15 13:25. Заголовок: Вот еще один пример ..


Вот еще один пример на забавные циклы. Соответствующее задание звучит следующим образом:

Заполнить двумерный массив единицами и нулями по следующему правилу. В первой строке все элементы должны иметь значение равное 1. Во второй строке каждый второй элемент устанавливается в 1, а все остальные - в 0. В третьей строке каждый третий элемент устанавливается в 1, а остальные элементы равны 0 и т.д.

Например, если имеется массив
 
const size_t M = 5;
const size_t N = 10;
int a[M][N];

то после инициализации он должен выглядеть следующим образом:
 
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
0 0 1 0 0 1 0 0 1 0
0 0 0 1 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 1

Выполнить поставленное задание можно с помощью следующих вложенных циклов:
#include <iostream> 

int main()
{
const size_t M = 5;
const size_t N = 10;
int a[M][N];

for ( size_t i = 0; i < M; i++ )
{
for ( size_t j = 0; j < N; j++ ) a[j] = ( j + 1 ) % ( i + 1 ) == 0;
}

for ( const auto &row : a )
{
for ( int x : row ) std::cout << x << ' ';
std::cout << std::endl;
}
std::cout << std::endl;
}

Эти забавные циклы появились в результате моего ответа на следующий вопрос на SO



Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 30.10.16 14:54. Заголовок: А каким образом без ..


А каким образом без тестового задания компания узнает о вашей квалификации? Проверит указанную в резюме информанцию? Тем более, когда вы junior и исправления в стандарт не вносили?

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 30.10.16 16:37. Заголовок: Во-первых, давайте н..


Во-первых, давайте начнем с того, что признаем, что все так называемые HR - это некомпетентные случайные люди. Все, на что они способны, это расклеить на заборах, коим в частности в наше время является интернет, объявления о вакансиях.

Чем некомпетентнее человек, тем он больше ориентируется на формальную сторону, то есть на бумаги. Сейчас даже некоторые кадровые агентства предлагают такую услугу, как написание для вас резюме. Фактически, устраивается конкурс на то, кто более красочно распишет свое резюме.

Я неоднократно встречался с такой ситуацией, когда совершенно никчемные программисты, которые, фактически, за свою профессиональную деятельность не написали ни строчки заслуживающего внимания кода, благодаря такому красочному резюме занимали высокие должности. Выглядит это примерно так. Числится такой человек в какой-то конторе на каком-то проекте и в своем резюме перечисляет все то, чем занимается контора, или что и как делается в проекте. Его собственный вклад в проект равен нулю. Он просто рядом присутствует., не будет преувеличением сказать, фактически, в качестве зрителя.

И чем меньше человек из себя представляет как специалист, тем больше он усилий тратит на написание красочного резюме. Каждый устраивается в жизни как может.

На собеседование надо приглашать тех людей, о которых вы уже имеете представление как о специалистах. И собеседование - это всего лишь дополнительный штрих к портрету того, о ком вы уже имеете твердое представление, как о специалисте, чтобы подтвердить правильность своего мнения.

Когда же созывают всех подряд, случайных людей, кому не лень было откликнутся на объявление о вакансии, то это говорит о том, что в конторе нет компетентного руководства.

Когда я учился в институте, то у нас был преподаватель математики, который говорил, что ему достаточно услышать первые одну-две фразы студента, чтобы понять, знает ли тот предмет или нет.

Я, например, участвуя в форуме на stackoverflow сразу же вижу по ответам участников, что они представляют из себя как специалисты. Порой смотришь профиль того или иного участника где написано, что он, к примеру - старший программист, а по его ответам видно, что он пишет код на уровне начинающего студента.

Квалифицированный программист - это общественный человек. Ему есть, что сказать другим, и есть, что обсудить с другими. А если этого нет, то какие бы красочные резюме он не писал бы о своем опыте, он - никто, и зовут его никак.

Что касается юниоров, то для юниора главное - это человеческие качества, стремление познавать новое, большой интерес к профессии, можно сказать, фанатизм.

Вот это и надо выявлять на собеседовании с юниорами. Надо проверять интеллект и общее развитие человека. А это легко выясняется из простой беседы с человеком. Всему остальному он научится. Было бы желание.

Приведу пример. Как-то я читал на персональном сайте краткую биографию одного автора многочисленных книг по программированию. Я потому заглянул на его сайт, что мне одна его книга понравилась. Написана она была профессионально. Так он упоминает такой случай в своей автобиографии, причем не единичный, когда он занимался одной технологией, например, в среде Windows, а его приглашали заниматься совершенно другой технологией в среде Unix, хотя он до этого ни с новой этой технологией, ни с Unix не имел дело. Если подходить с позиций того, как часто ныне проходят собеседования, то такие переходы просто не возможны, так как упомянутый персонаж, как я уже сказал, ничего в новом для себя проекте не знал. В результате бездари будут просиживать штаны на проектах, а талантливые программисты будут лишены возможности проявить свой талант.


Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 30.10.16 18:08. Заголовок: Ну не знаю, не кажды..


Ну не знаю, не каждый хороший программист обязательно должен писать гайды или отвечать на stackoverflow. Тем более, что зачастую при участии в сложных проектах на это просто нет времени. Если же компании нужны знания определённой технологии, то взять такого человека просто по написанному в резюме как минимум опасно.

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 01.11.16 00:53. Заголовок: Каждый квалифицирова..


Каждый квалифицированный программист должен быть открытым для сообщества программистов, потому что ему есть что сказать другим. Если этого нет, значит программист еще не созрел как программист. Только и всего.

Просто многие о себе очень большого самомнения, а на проверку оказывается, что они, как я уже писал, - никто, и зовут их никак.

Участие в сложных проектах как раз дает богатую пищу для генерирования идей и обсуждению их с другими программистами. Ссылки на то, что, якобы, нет времени, говорит только о незрелости программиста. Я думаю, например, что Герб Саттер участвовал и участвует во многих сложных проектах, к тому же он еще возглавляет Комитет по стандартизации C++, тем не менее у этого человека много статей, книг и других материалов, которыми он делится с сообществом программистов.


Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 12.01.17 14:16. Заголовок: Задача с циклами


Сыроежка
Если интересно, я вот такое написал

for (int j = 0; j < N; j ++)
{
int s=1;
if(j%2==0){
s=0;
}
for (int i = s; i < M; i+=2){
std::cout << mas[j] << " ";
}
std::cout << std::endl;
}


Спасибо: 0 
Цитата Ответить



ссылка на сообщение  Отправлено: 14.01.17 00:56. Заголовок: W пишет: Если интер..


W пишет:

 цитата:
Если интересно, я вот такое написал



Только когда используете переменную с именем i в квадратных скобках, то с обоих сторон вставляйте пробел. Иначе это рассматривается как тег выбора курсивного шрифта.

Например,

 
mas[ i ]

Что касается самого кода, то, я думаю, вы имели в виду, что в условии внешнего цикла должна быть переменная M , а в условии внутреннего цикла должна использоваться переменная N, так как массив объявлен, как имеющий M строк и N столбцов, не так ли?

Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 31
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет