Страница 2 из 2 < 1 2
Показывать 40 сообщений этой темы на одной странице

Javascript-форум (https://javascript.ru/forum/)
-   Оффтопик (https://javascript.ru/forum/offtopic/)
-   -   Задачка на сообразительность (https://javascript.ru/forum/offtopic/15269-zadachka-na-soobrazitelnost.html)

with-love-from-siberia 20.02.2011 22:36
float,
значит надо переделать алгоритм, чтобы итераций было не больше чем символов в строке. Посмотрите мой пост выше.

B@rmaley.e><e 20.02.2011 22:37
with-love-from-siberia, приведите код, а я придумаю контрпример (не забудьте протестировать для начала на уже имеющихся примерах).

monolithed 20.02.2011 23:21 
String.prototype.at = function(str) {
    var tl = this.length, sl = str.length;
    for(var i=j=0; i<tl; i++) {
        if(this[i] == str[j] && sl == ++j) return ++i-j;
    }
    return -1;
}

var s1 = 'aababababaO_o', l1 = 'ababaO', l2 = 'abac', l3 = 'aa', l4 = 'O_o';

alert([
    [s1.at(l1), s1.indexOf(l1)],
    [s1.at(l2), s1.indexOf(l2)],
    [s1.at(l3), s1.indexOf(l3)],
    [s1.at(l4), s1.indexOf(l4)]
].join('\n') );


:)

float 20.02.2011 23:33 
String.prototype.at = function(str) {
    var tl = this.length, sl = str.length;
    for(var i=j=0; i<tl; i++) {
        if(this[i] == str[j] && sl == ++j) return ++i-j;
    }
    return -1;
}

var s1 = 'aababababaO_o', l1 = 'aabaO', l2 = 'abac', l3 = 'aa', l4 = 'O_o';

alert([
    [s1.at(l1), s1.indexOf(l1)],
    [s1.at(l2), s1.indexOf(l2)],
    [s1.at(l3), s1.indexOf(l3)],
    [s1.at(l4), s1.indexOf(l4)]
].join('\n') );

:)

B@rmaley.e><e 20.02.2011 23:34 
String.prototype.at = function(str) {
    var tl = this.length, sl = str.length;
    for(var i=0, j=0; i<tl; i++) {
        if(this[i] == str[j] && sl == ++j) return ++i-j;
    }
    return -1;
}

var s1 = 'ababc', l1 = 'abac';

alert([
    [s1.at(l1), s1.indexOf(l1)]
].join('\n') );

monolithed 20.02.2011 23:41 
String.prototype.at = function(str) {
    var tl = this.length, sl = str.length;
    for(var i=j=0; i<tl; i++) {
        if(this[i] == str[j] && sl == ++j && sl != i) return ++i-j;
    }
    return -1;
}

var s1 = 'ababc', l1 = 'abac', l2 = 'bc', l3 = 'aa', l4 = 'O_o';
 
alert([
    [s1.at(l1), s1.indexOf(l1)],
    [s1.at(l2), s1.indexOf(l2)],
    [s1.at(l3), s1.indexOf(l3)],
    [s1.at(l4), s1.indexOf(l4)]
].join('\n'));


:D

B@rmaley.e><e 20.02.2011 23:48 
String.prototype.at = function(str) {
    var tl = this.length, sl = str.length;
    for(var i=j=0; i<tl; i++) {
        if(this[i] == str[j] && sl == ++j && sl != i) return ++i-j;
    }
    return -1;
}

var s1 = 'aabac', l1 = 'abac';
 
alert([
    [s1.at(l1), s1.indexOf(l1)]
].join('\n'));

float 20.02.2011 23:50
ааай. Ребят. Сложность в том, что при достаточной длине строки, на определённом этапе создаются перекрывания. Их число подстрока-1(так вроде), т.е. функция зависит от параметров.
monolithed
else блок там не для красоты стоит

with-love-from-siberia 21.02.2011 00:10
Цитата:
Сообщение от B@rmaley.e><e
приведите код
Давайте наоборот. Простите, но мне уже лениво сегодня заниматься задачками для 1-2 курса спецфак-та. Я привел неполное словесное описание алгоритма. Предлагаю форуму завершить его формулировку и все вопросы отпадут.

Ну может быть завтра напрягусь (-:

float 21.02.2011 00:34
Цитата:
Я привел неполное
Что-то в нём я не заметил путь обхода проблемы описанной выше.

FINoM 21.02.2011 05:57
Еще одна задачка.
Есть два массива, которые генерируете вы (не суть из каких данных, главное, что вы имеете возможность создать свою структуру и тип элементов Number или String). В первом массиве содержится элемент, равный одному из элементов из второго массива. Пример: 
arr1 = ['a', 'b', 'c', 'd'];
arr2 = ['e','f','g','b','h','i'];

Повторюсь, структура массива произвольная, задаваемая вами. Количество элементов массивов велико, вплоть до 1 миллиона.
Задача
Найти индексы совпадающих элементов, написав максимально оптимизированный для этой цели код и предложить структуру массива (если она отличается от указанной выше).

Matre 21.02.2011 06:21 
function find(A, B) {
	R = [-1, -1];
	outer: for (var i = 0; i < A.length; i++) {
		for (var j = 0; j < B.length; j++) {
			if (A[i] == B[j]) {
				R = [i, j];
				break outer;
				break;
			}
		}
	}
	return R;
}


(R[0] + 1) * (R[1] + 1) итераций.

function find(A, B) {
	var C = {}, R = [-1, -1];
	for (var i = A.length - 1; i >= 0; i--)
		C[A[i]] = i;
	for (var i = 0; i < B.length; i++) {
		if (B[i] in C) {
			R = [C[B[i]], i];
			break;
		}
	}
	return R;
}


A.length + R[1] - 1 итераций.

Vulkan 21.02.2011 10:33
По первой задаче получилось немного громоздко, но работает вроде как надо:
String.prototype.index = function(sep) {
        var l = this.length, sl = sep.length - 1, i = 0, j = 0, w = '';
        while (i < l) {
            if ((this.charAt(i) == sep.charAt(0) && this.charAt(i + sl) == sep.charAt(sl)) || j != 0){
                if (j <= sl) {w += this.charAt(i + j); j++;}
                else if (j >= sl) if (w == sep) return i; else {w = ''; j = 0; i++; continue;}} else i++;}
        return -1;
    }

    var s1 = 'aababaO_o',
        s2 = 'aababababaO_o';
    l1 = 'aba', l2 = 'abac', l3 = 'aa', l4 = 'O_o', l5 = 'abaO', l6 = 'ababaO';

    alert([
        [s1.index(l1), s1.indexOf(l1)],
        [s1.index(l2), s1.indexOf(l2)],
        [s1.index(l3), s1.indexOf(l3)],
        [s1.index(l4), s1.indexOf(l4)],
        [s1.index(l5), s1.indexOf(l5)],
        [s2.index(l6), s2.indexOf(l6)]
    ].join('\n'))

B@rmaley.e><e 21.02.2011 10:35
FINoM, если поддерживать отсортированность массивов (грозит вставкой за O(n), лучше использовать списки), то можно найти такую пару за O(n+m), где m и n - длины массивов.

Или использовать вместо массива какое-нибудь сбалансированное дерево. Вставка в среднем O(log n), поиск пары - O(n+m).

B@rmaley.e><e 21.02.2011 10:39
Vulkan, учитывая то, что i увеличивается не на каждой итерации, этот вариант по алгоритмической сложности ничем не отличается от двух циклов.

Matre 21.02.2011 10:39
***

FINoM 21.02.2011 17:46
Matre, B@rmaley.e><e, даю подсказку:

Первый массив создаем "традиционно"
arr1 = {1:'a', 2:'b', 3:'c', 4:'d'};


Во втором при создании меняем ключи и значения местами
arr2 = {'e':1,'f':2,'g':3,'b':4,'h':5,'i':6};

micscr 23.02.2011 11:54
Цитата:
Сообщение от FINoM (Сообщение 93463)

Первый массив создаем "традиционно"
arr1 = {1:'a', 2:'b', 3:'c', 4:'d'};
традиционно - специально в кавычки заключил? Как бы объект создаешь ...

FINoM 23.02.2011 13:05
Цитата:
Сообщение от micscr (Сообщение 93647)
традиционно - специально в кавычки заключил? Как бы объект создаешь ...
Это для наглядности. На самом деле это обычный массив.


Часовой пояс GMT +3, время: 10:43.
Страница 2 из 2 < 1 2
Показывать 40 сообщений этой темы на одной странице