Решение математических задач на PureBasic

Помогите пожалуйста, сижу далеко не один день ломаю голову, читаю в интернете, ну не получается решить задание.
Нужна лишь одна функция(Procedure)
она получает лишь один параметр, и одно число на выходе
есть двумерный массив, например ввиде таблицы:
__1 2 3 4 5
1| 0 0 0 1 0
2| 0 0 0 0 1
3| 0 0 0 1 1
4| 1 0 1 0 0
5| 0 1 1 0 0
в данном примере число 5 это и есть тот параметр, который получает функция, то есть сколько на сколько будет массив
и уже заранее массив известен и заполнен
представьте что это 5 городов, а цифра 1 означает между которыми есть дорога, 0 между которыми нет дорог
число которое рассчитывает функция, это между сколькими городами есть путь
например из 1 города можно попасть в город 2: 1-4-3-5-2
из 4 города в первый: 4-1
например
a=func(b)
a - число между сколькими городами есть путь
b - число, сколько всего городов
массив с городами уже заполнен
заранее прям огромное спасибо, если прям кодом поможете, это очень сильно меня спасёт

0

на сколько я понял дана сумма городов, и таблица. Нужно исходя из этой таблицы вернуть сумму дорог между городами...
код дать не смогу, но если сможеш строки запихнуть в масивы, типа строка1=dim1 то както так:
procedure.i (kolichestvo_gorodov.i)
i.i = kolichestvo_gorodov.i
dim t.i(i) пытаемся создать масивы для городов, то есть где масив 1(сумма городов)=первому городу/ хз получится ли
for ii=1 to i ;создаём цикл для города
dim a.i= ... впихиваем в масив a значение строки ii
с.i=0 обнуляем количество дорог для текущего города
for iii=1 to i ;проверяем наличае путей между текущим городом и остальными
if a(iii)=1 если есть дорога
c=c+1 то плюсуем единичку к сумме дорог для текущего города
endif завершааем условие проверки наличия дорог
next завершаем цикл сумировани наличия дорог для текущего города
t(ii)=c присваиваем переменной масива количество дорог
next переходим к следующему городу
return (t) хотя хз как правильно вернуть массив
endproceddure
в результате имеем масив где в переменной 1 соответствующей первому городу содержится количество дорог соединяющих его с остальными, то же для других городов

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

0

В примере есть несоответствие. Указано что 1 - есть дорога, но в тоже время, утверждается что имеется путь между городами, которые в таблице отмечены нулями.
Почему первая диагональ нулей отмечена красным цветом? А вторая диагональ (в которой тоже нули) никак не отмечена?

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

1

Shaggy74,
ежели же нужна сумма всех путей между городами то вставь п процедуру ещё следующий цикл
for s=1 to i
total=t(s)+total
next
return total

1

Сообщение от locm В примере есть несоответствие. Указано что 1 - есть дорогоа, но в тоже время, утверждается что имеется путь между городами, которые в таблице отмечены нулями. Почему диагональ нулей отмечена красным цветом? А вторая диагональ (в которой тоже нули) никак не отмечена?

1-это дорога напрямую, например из города 1 в город 4 есть путь
но и из города 1 в город 2 есть путь, функция и должна сама его найти, потому что напрямую нет дороги, но через другие города можно добраться
красным цветом нули отметил, просто что впринципе не возможно дороги из города 1 в город 1, или из города 2 в город 2

Добавлено через 8 минут
logincyberforu, спасибо, сейчас поразбираюсь

0

Сообщение от Shaggy74 1-это дорога напрямую, например из города 1 в город 4 есть путь но и из города 1 в город 2 есть путь, функция и должна сама его найти, потому что напрямую нет дороги, но через другие города можно добраться красным цветом нули отметил, просто что впринципе не возможно дороги из города 1 в город 1, или из города 2 в город 2

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

1

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

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

0

Shaggy74, упс не внимательно прочёл... в таком случае может быть возвращён только двумерный массив, где значения первого масива есть название города, а значения второй степени вариации путей, но таких вариаций будет уйма, так как каждый город соединён как минимум сдвумя городами (по идее) и при поиске путей количество членов второго масива будет возрастать пропорционально количестве 1 для данного города. То есть прога найдёт пути через все города с которыми данный город имеет дороги, но более того она найдёт и дороги через все вторые города и даже до нного количества кругов между двумя городами а затем путь к третьему, то есть результат будет огромен...

Добавлено через 5 минут
Shaggy74, наврятли ты сможеш обдумать такой алгоритм... в результате никак не может быть одна переменная, при общем количестве городов. то есть перефразирую тебя: если есть карта и 16783 городов то как мне проехать от неизвестно откуда в неизвестно куда? согласись звучит дико. Вероятно ты имел в виду рассчитать одной функцией кратчайший путь от начального города до конечного, но в таком случае асчёт будет только теоритическим... так как вместо 1 лучше написать расстояние между городами.


вобщемто я не полностью уловил суть вопроса.... вероятно

1

сейчас попробую понятней изложить
вложил к сообщению картинку, сразу скажу что на скорую руку сделал, на картинке по сути изображена табличка с 1 поста только графически
задача в чём
из 1 города во второй можно попасть? -да
1-4-3-5-2
значит +1
из 1 города можно попасть в третий? -да
1-4-3
значит ещё +1
и так далее до пятого
следующий второй город:
из второго можно попасть в третий? -да
2-5-3
значит +1
и так далее к пятому
и так все города, а итог это всё что мы на складывали +1
у меня в голове есть идея алгоритма, но не могу в код реализовать

Миниатюры

 

0

Shaggy74, добавь линию между городом 1 и 2 и получится пипец, - то есть из города 3 в город 4 можно будет попасть не только 3-4 но и 3-5-2-1-4. или 3-5-2-1-2-1-5 но этот вариант можно исключить... а если будет дорога межу городами 1 и5 то опять же 3-5-1-4, тут конечно на первый взгляд возникает мысль чем меньше городов тот результат и нужен, но что если количество городов равное? И не стоит забывать что функция получает только сколичество городов то есть в нашем примере 5 а что если нужно попасть из города 3 в город 4 ?

1

Сообщение от logincyberforu добавь линию между городом 1 и 2 и получится пипец, - то есть из города 3 в город 4 можно будет попасть не только 3-4 но и 3-5-2-1-4

а мне надо что бы считало за 1 путь, то есть если есть путь между 3 и 4 городами то прибавляет один, вне зависимости сколько путей
из города 3 в город 4 можно попасть напрямую, так же прибавляется один
в итоге не будет заоблочного результата

0

Shaggy74, то есть тебе сам путь не нужен, нужна только сумма всех возможных путей?

1

да, путь не нужен, нужно число - количество пар городов между которыми реально построить путь

0

Shaggy74, тогда если не учитывая длину и при обязательном условии что из каждого города ведёт не менее двух дорог:
procedure way(summa) начинаем процедуру где в качестве исходного есть количество гороов
dim cyty(summa) создаём массив для хранения путей для конкретного города
for i=1 to summa начинаем цикл для данного города
w=0 обнуляем счётчик путей который остался от прошлого города
dim d = впихиваем в масив строку i
for ii=1 to summa запускаем цикл подсчёта путей из города
if d(ii)=1 если из города есть дорога к другому городу то
w=w+1 прибавляем к сумме дорог 1
next заканчиваем цикл подсчёта дорог для данного города
cyty(i)=w-1 присваем городу количество путей и вычитаем путь по которому мы приехали в него (дабы не делать круги)
next заканчиваем цикл присвоения количества дорог для городов
for i=1 to summa начинаем цикл общего подсчёта путей
total=total*cyty(i) сам процесс подсчёта путей так как кроме той дороги которая нас привела в определённый город есть ещё не менее одной дороги которая предложит не менее одной дороги.......... которая приведёт на к цели
next заканчиваем цикл общего подсчёта

результат будет приблизительным, я гдето забыл еденичку, то есть если города будут расположены в кольце то будет две дороги но функция вернёт 1, вроде
return total

что же касается самой идеи умножения исходящих дорог за вычетом одной, спорить не буду, проверь на примере 4х городов. Функция вернёт общее количество сумм всех возможных путей. (приблизительно грю же гдето 1 забыл) хотя зачем тебе такая инфа ума не приложу...
упс пар городов... ну по идее надо тогда число под корень загнать или на чтото разделить... но если из каждого города выходит минимум две дороги то алгоритм будет иной..
хотя загнался я уже...

1

блин что-то реально слишком всё) попробую свои мысли сформулировать)

0

Как много букв...

Это задача формулируется так: дана матрица смежности неориентированного графа. Нужно определить связен граф или нет.

Если граф связен, то из любого города можно попасть в любой.

0