Предлагаю размяться и решить задачу, (которую я сам придумал)

[promov]

2 года назад как подзадачу при решении общеизвестной задачи о Ханойской башне. Каким образом одна задача оказалась связана с другой, я сейчас не вспомню, да это и не важно. Вот условие:

Имеется набор аb из символа а и символа b, условимся поэтому
1)считать его длину равной 2;
2)Символы а и b считать противоположными;
При задании программе целого положительного числа х, причём х>=2, образуется новый набор символов, состоящий только из символов а и b, отвечающий следующим условиям:
1) он состоит из количества символов (его длина равна) 2 в степени х;
2) последовательность символов в нём есть точная копия такого набора сиволов, чья длина равна 2 в степени (х-1) плюс ещё одна точная копия такого набора сиволов, чья длина равна 2 в степени (х-1);
3) В наборе символов, чья длина равна 2 в степени х, последний символ противоположен последнему символу в наборе, чья длина равна 2 в степени (х-1). Иллюстрация:

Начальный набор_______________________________________________________ав
Программе задано число 2, получился набор________________________аваа
Программе задано число 3, набор_______________________________авааавав
Программе задано число 4, набор_____________________авааавававаааваа
И так далее.

Требуется написать программу или просто алгоритм по реализации этой задачи. Ну или идею, хотя бы. Обсуждаем, в общем. У меня получилось. С уважением, promov.

[eduard_pustobaev]

Мегазадача...

[promov]

Говори

[sergio]

Требуется написать программу

Издеваетесь что ли, с утра пораньше?? Тут условия понимать дольше чем делать.

Программе задано число 2, получился набор________________________аваа

$ ./a.out 2
0100

Программе задано число 3, набор_______________________________авааавав

$ ./a.out 3
01000101

Программе задано число 4, набор_____________________авааавававаааваа

$ ./a.out 4
0100010101000100
01000101010001000100010101000101
0100010101000100010001010100010101000101010001000100010101000100

Но баш за баш. Вот вам ответная задача:

Код: Выделить всё

$ cat __t.cpp

  #include <iostream>
  #include <string>
  #include <stdlib.h>

using namespace std;

string megazadacha(string s, int n)  {
  if (1 == n)  return s;
  string t = s;
  (* t.rbegin()) = '0' + ! (int)(* t.rbegin() - '0');
  return  megazadacha(s + t, --n);
}

int main(int argc, char* argv [])  {

string s("01");
int n = atoi(argv[1]);
cout << megazadacha(s, n) << std::endl;

  return  0;
}

Это - самый ужасный код который можно было написать с утра пораньше.
Ваша задача - найти в нем все ошибки и привести к нормальному виду.
Допольнительное условие - на чистом Си.

[promov]

Без разговоров, Как продвинусь в С (дело вроде бы пошло, тьфу-тьфу-тьфу) так за вашу задачу возьмусь. А Ваше решение я не понял. Программе может быть задано любое число, удовлетворяющее условию, например 98. И вот машина должна выдать длинный-длинный перечень из а и b, удовлетворяющий условию. Можно вручную, конечно, но это ерунда будет полная. Условие я коряво, может быть, прописал, но, думаю, из иллюстрации всё понятно.

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

[sergio]

А Ваше решение я не понял. Программе может быть задано любое число, удовлетворяющее условию, например 98. И вот машина должна выдать длинный-длинный перечень из а и b, удовлетворяющий условию.

Опять издеваетесь? К вашем сведению, максимальное число, поддерживаемое на i386/amd64 встроенными средствами - long long, оно 64 бита, ака 2^64. А "любое число, удовлетворяющее условию, например 98" - это 2^98. Попробуйте собрать этот код и запустить его с аргументом 98. (Шутка).
Я не буду злобствовать с большими числами, форум засорять, вот вам результат для 10:

Код: Выделить всё

$ ./a.out 10
01000101010001000100010101000101010001010100010001000101010001000100010101000100
01
00010101000101010001010100010001000101010001010100010101000100010001010100010101
00
01010100010001000101010001000100010101000100010001010100010101000101010001000100
01
01010001000100010101000100010001010100010101000101010001000100010101000100010001
01
01000100010001010100010101000101010001000100010101000101010001010100010001000101
01
00010101000101010001000100010101000100010001010100010001000101010001010100010101
00
01000100010101000101010001010100010001000101010001010100010101000100010001010100
01
00010001010100010001000101010001010100010101000100010001010100010101000101010001
00
01000101010001010100010101000100010001010100010001000101010001000100010101000101
01
00010101000100010001010100010001000101010001000100010101000101010001010100010001
00
01010100010001000101010001000100010101000101010001010100010001000101010001010100
01
01010001000100010101000101010001010100010001000101010001000100010101000100010001
01
0100010101000101010001000100010101000100

Так что прежде чем ставить задачу в программировании с 98, надо хотя б понимать математику вопроса.

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

Разумеецо. =) Если "давно" - это в досовском компиляторе, то там int 16битный, ака 2^16. Вот у вас задача и "закончилась" на аргументе 16.

[promov]

Да я прекрасно понимаю что мощности машины ограничены, я к примеру говорю 98. Ещё раз: набирать надо не вручную, иначе задача задачей и не была бы. И практического смысла в ней искать не надо, его в ней нет. Это просто упражнение, понимаете? Поупражняться то есть, кому интересно.

[sergio]

Да я прекрасно понимаю что мощности машины ограничены, я к примеру говорю 98. Это просто упражнение, понимаете? Поупражняться то есть, кому интересно.

Ну поупражнялись. Соберите код и проверьте, то он делает, что вам хотелось или нет. Аргументы больше 30-31 использовать не рекомендую. С аргументом 32 результирующая строка будет иметь длину около 4 гигабайт, еще 2 потребуются для ее копирования, плюс фрагментация, а если у вас i386, то их у вас всего около трех ГБ. Кроме того, длина строки переполнится (и скорее всего на амд64 тоже, она наверняка int-ом...). Так что на амд программа "закончит" работу так же, как у вас на 16-битом инте, только сперва сожрет всю память и раздует своп. А на 386 свалится с оут ов мемори. (Это я так предполагаю, не проверял). Да, кроме того, в библиотеке может стоять ограничение на единовременно выделяемый new/alloc объем - тогда она из-за него "закончится".

[Славик]

Да я прекрасно понимаю что мощности машины ограничены, я к примеру говорю 98. Ещё раз: набирать надо не вручную, иначе задача задачей и не была бы. И практического смысла в ней искать не надо, его в ней нет. Это просто упражнение, понимаете? Поупражняться то есть, кому интересно.

Навскидку задача сводится к перебору пар строк заданной в условии длины. Единственое дополнительное условие которому должны удовлетворять искомые строки - разные последние символы? Я правильно понял? Количество вариантов должно расти в геометрическо прогрессии.

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

[promov]

Я в С не силён, но предполагаю, что Вы написали код для вводимого числа, равного 10. А для числа 100 размер кода будет в 10 раз больше предложеного Вами.
Если так, что ж, спасибо за участие. Добавлю лишь, что величина кода, написанного мной не зависела от того, какое число вводилось: 4 или 15. И он был программа, а не готовое решение, найденное вручную... Извините.

[sergio]

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

4x4 руками подбирал, это недолго. =)
А дальше там число перестанок тоже растет хорошо, можно легко поставить задачу так, что машина до вечера не переберет. =)
С маг квадратами там было, кажется, какое-то дополнительное условие, сильно упрощавшее решение? В "ходе коня" точно было...

Я в С не силён, но предполагаю, что Вы написали код для вводимого числа, равного 10. А для числа 100 размер кода будет в 10 раз больше предложеного Вами.

Какой код??? программный или результат??? Программный один для любых чисел в пределах поддерживаемых машиной. Результат для 100 на входе будет никак не в 10 раз больше, а кажется в 2^90 раз больше. Математика, еще раз.

Если так, что ж, спасибо за участие. Добавлю лишь, что величина кода, написанного мной не зависела от того, какое число вводилось: 4 или 15. И он был программа, а не готовое решение, найденное вручную... Извините.

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

[promov]

Навскидку задача сводится к перебору пар строк заданной в условии длины. Единственое дополнительное условие которому должны удовлетворять искомые строки - разные последние символы? Я правильно понял? Количество вариантов должно расти в геометрическо прогрессии.

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

Если ты имел ввиду такое: копируем строку, изменяем в ней последний элемент. Потом снова копируем получившуюся строку и снова изменяем в ней последний элемент... Ну чтож, это тоже решение (как и набрать вручную), Только не надо, наверное, так задачки решать...
Я неправ? В любом случае, скоро я представлю своё решение, зацените.

К разговору про квадрат потом вернёмся.

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

Об этом-то я как раз и не беспокоюсь, это дело времени... Cкорого, смею думать. По задаче: у Вас всё?

[sergio]

По задаче: у Вас всё?

Разумеется, о чем тут говорить? Не понял, вы скомпилировали мой код?
Это вот так:
g++ имя_файла.cpp
запустили с разными числа? результат видели? это вот так:
./a.out число
Еще вопросы остались? остались - давайте, нет - я пошел.

[promov]

Подождите. А сам-то код где? Вы же выложили готовое решение, как я понял. А где начало, конец, объявление переменных, циклы там разные... Это всё где?

[sergio]

Подождите. А сам-то код где? Вы же выложили готовое решение, как я понял. А где начало, конец, объявление переменных, циклы там разные... Это всё где?

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

[promov]

Но баш за баш. Вот вам ответная задача:
Это - самый ужасный код который можно было написать с утра пораньше.
Ваша задача - найти в нем все ошибки и привести к нормальному виду.
Допольнительное условие - на чистом Си.

Ну извините, уважаемый. Никак не мог предположить, что "ответная задача" есть "ответ на задачу"... Обязательно разберусь и подправлю!
Решили-решили, молодцом. Компактно решили, cудя по всему.

[diesel]

Но баш за баш. Вот вам ответная задача:
Это - самый ужасный код который можно было написать с утра пораньше.
Ваша задача - найти в нем все ошибки и привести к нормальному виду.
Допольнительное условие - на чистом Си.

Ну извините, уважаемый. Никак не мог предположить, что "ответная задача" есть "ответ на задачу"... Обязательно разберусь и подправлю!
Решили-решили, молодцом. Компактно решили, cудя по всему.

там нет ничего страшного. решение твоей задачи сводится к написанию функции, которая:
1) если вводится 1 - возвращает само значение - т.е. ab
2) если вводится другое число, то вычисляет предыдущее значение результата(вызовом этой же самой функции еще раз, но уже с числом на единицу меньшим), дублирует его, и в случае необходимости меняет последнюю букву.

примерно это тебе в решении и написали.

[Славик]

Если ты имел ввиду такое: копируем строку, изменяем в ней последний элемент. Потом снова копируем получившуюся строку и снова изменяем в ней последний элемент... Ну чтож, это тоже решение (как и набрать вручную), Только не надо, наверное, так задачки решать...
Я неправ? В любом случае, скоро я представлю своё решение, зацените.

Зачем последние символы менять?
N=Длина_строки_по_условию - 1;
Тупо из программы перебираем строки длиной N, можно во вложенных циклах. Во внешнем цикле в конец дописываем сначала а потом бэ, во вложенном наоборот. А потом энто соединяем. Трудность только в количестве вариантов и размерах строк, которые зашкаливают оч быстро.

[sergio]

Согласно чьему-то утверждению, любая рекурсия может быть превращена в цикл. Эта - точно может. =)

Код: Выделить всё

  #include <iostream>
  #include <string>
  #include <stdlib.h>

  using namespace std;


int main(int argc, char* argv [])  {

  string s("01");
  int n = atoi(argv[1]);

  while  (1 != -- n)  {
    string t = s;
    (* t.rbegin()) = '0' + ! (* t.rbegin() - '0');
    s.append(t);
  }
  cout << s << endl;
  return  0;
}

[promov]

Понял. Cхематично предложенные решения вне зависимости от их реализации на практике можно представить так:
1)
a) копируем аb;
b) cоединяем ab и ab. Получаем abab;
c) изменяем в abab последний знак на противоположный. Получаем abaa;
2)
a) копируем аbaa;
b) cоединяем abaa и abaa. Получаем abaaabaa;
c) изменяем в abaaabaa последний знак на противоположный. Получаем abaaabab;
И так далее.
Но! Когда я решал эту задачу по техническим причинам не мог использовать массивы и строки. Тем не менее, я её решил в таких условиях. Уверен, получится и у вас. Работаем то есть только с отдельными символами (следовательно, не можем скопировать строку, дабы её присоединить к уже имеющейся).

В общем, вот... Усложнил условия. Никаких массивов и строк. Решение есть.

[Славик]

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

4x4 руками подбирал, это недолго. =)
А дальше там число перестанок тоже растет хорошо, можно легко поставить задачу так, что машина до вечера не переберет. =)
С маг квадратами там было, кажется, какое-то дополнительное условие, сильно упрощавшее решение? В "ходе коня" точно было...

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

[sergio]

В общем, вот... Усложнил условия. Никаких массивов и строк. Решение есть.

Что-то я не понял, что имеется в виду... что надо каждую букву конечной последовательности высчитывать по-отдельности и выводить, и так все, одну за другой?? Мазохизмом отдает, но если есть любители... гляну на решение. Мне лень. =)

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

Ради интереса когда-то начинал и часть тупиковых вариантов отсекал. Но потом бросил. =)
Перебором там (n ^ 2)! / 4 перестановок что ли, и уже для n 5-6 число безумное. =)

Ход коня - частный случай.

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

[promov]

В общем, вот... Усложнил условия. Никаких массивов и строк. Решение есть.

Что-то я не понял, что имеется в виду... что надо каждую букву конечной последовательности высчитывать по-отдельности и выводить, и так все, одну за другой?? Мазохизмом отдает, но если есть любители... гляну на решение. Мне лень. =)

Именно. Ключевое слово "высчитывать". Понятное дело. не вручную их прописывать, а алгоритм должен определять какая буква должна в каком месте стоять. Для любого введённого числа n. Ну не знаю, мне интересно было решить. Ещё раз: не работаем с массивами и строками, а только с отдельными символами.

[sergio]

В общем, вот... Усложнил условия. Никаких массивов и строк. Решение есть.

Есть, есть кто б сомневався... "Что один человек сделал, то другой всегда поломать сможет..."
В остром приступе ночного мазохизма задача была решена. Правда, пока толком не понял, как. Но результат идентичен тому коду, который строчки двигал...
В программе и двадцати строк нет, так что желающие могут подключаться к поискам святого грааля.
Кстати, автор вопроса как - готов предъявить общественности свой вариант ответа?

[promov]

Никаких строк. Вы ограничены в средствах так: строки и массивы в памяти компьютера не представлены никоим образом.
Алгоритм готов, конечно, представить. Программу-то любой после напишет.
Могу дать подсказку, в каком направлении думать.

[sergio]

Никаких строк. Вы ограничены в средствах так: строки и массивы в памяти компьютера не представлены никоим образом.
Алгоритм готов, конечно, представить. Программу-то любой после напишет.
Могу дать подсказку, в каком направлении думать.

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

[promov]

Не сомневаюсь, что будут все пояснения.

[sergio]

Не сомневаюсь, что будут все пояснения.

Нет, зачем же?? Все пояснения каждый себе ищет сам. Не люблю лентяев. Щас они тут послушают, ушами похлопают, и скажут: "А, ерунда, сделать раз плюнуть." Фиг вам сразу так пояснения будут, хехе.
Логика работы старого решения - надеюсь, всем понятна? вопросов нет?
Ну вот вам два кода тогда, старый (он там, в начале ленты; замените '0' на 'a' и '1' на 'b' соотв-но) и новый, соберите, прогоните и сравните результаты. (У меня сошлись.) Утренний свежий взгляд позволил повыкидвать еще несколько строк. Ошибки какие-нибудь найдутся, я в битовых операциях не рублю, но работает.

Код: Выделить всё

$ gcc -Wall -std=c99 -s -o newcode test.c
$ g++ -Wall -s -o oldcode __t.cpp
$ ./oldcode 20 > _old.txt
$ ./newcode 20 > _new.txt
$ diff _old.txt _new.txt;  echo "// $? //"
// 0 //
$

Код: Выделить всё

$ cat test.c

  #include <stdio.h>
  #include <stdlib.h>
  typedef unsigned int uint;

  int main(int argc, char* argv [])  {
    int n = 1 << (atoi(argv[1]) - 1);
    int bits = 0;
    for (uint m = ~ 0U ^ ~ 0U >> 1U;  0U != m;  m >>= 1U)  ++ bits;
    for (int i = 1;  i <= n;  ++ i)  {
      putchar('a');
      int r = 0;
      uint x = i;
      for (uint m = ~ 0U ^ ~ 0U >> 1U;  0U != (x &= ~ m); m >>= 1U)  ++ r;
      putchar((0 != (bits - r) % 2)  ?  'b'  :  'a');
    }
    putchar('\n');
    return  0;
   }

М-да можно еще попроще:

Код: Выделить всё

$ gcc -Wall -std=c99 -s -o newcode test.c
$ gcc -Wall -std=c99 -s -o newcode2 test2.c
$ g++ -Wall -s -o oldcode __t.cpp
$ ./oldcode 20 > _old.txt
$ ./newcode 20 > _new.txt
$ ./newcode2 20 > _new2.txt
$ diff3 _old.txt _new.txt _new2.txt;  echo "// $? //"
// 0 //
$

Код: Выделить всё

$ cat test2.c

  #include <stdio.h>
  #include <stdlib.h>
  typedef unsigned int uint;

  int main(int argc, char* argv [])  {
    uint n = 1 << (atoi(argv[1]) - 1);
    for (uint i = 1;  i <= n;  ++ i)  {
      putchar('a');
      int r = 1;
      for (unsigned int m = 1U;  0U == (i & m); m <<= 1U)  ++ r;
      putchar((0 != (r % 2))  ?  'b'  :  'a');
    }
    putchar('\n');
    return  0;
   }

Версию от автора вопроса мы когда увидим?

Кто-то гостей назвал, было "33 чел. читают эту тему (гостей: 32, скрытых пользователей: 0)"...
Теперь все убежали, никто ничего не сказал...

[promov]

Раз Вы не хотите давать пояснения, придётся разбираться самому, на это уйдёт некоторое время. Cвой алгоритм готов представить хоть сейчас, но я должен хотя бы знать, отличен он от Вашего или нет. Дабы не тратить время на вопросы, предположу что Вас устроит ответ только типа Вашего: код. Чтож, буду писать код. Это время. В следующее моё появление на форуме (не в этой конкретно теме, а именно на форуме) я буду готов выложить код.

[Славик]

Не сомневаюсь, что будут все пояснения.

Нет, зачем же?? Все пояснения каждый себе ищет сам. Не люблю лентяев. Щас они тут послушают, ушами похлопают, и скажут: "А, ерунда, сделать раз плюнуть." Фиг вам сразу так пояснения будут, хехе.
Логика работы старого решения - надеюсь, всем понятна? вопросов нет?

Поскольку топик вывешен в разделе для начинающих, думаю, нужны пояснения. Во всяком случае совсем начинающим это не интересно, поскольку непонятно, а совсем не начинающие сюда, возможно, и не заглянут. Когда начинающий разовьётся до уровня понимания этих исходников, ему, возможно, это будет уже не интересно. Мну думает вот так =)