search

divyang4481 / mipt-hw

Automatically exported from code.google.com/p/mipt-hw
0 stars 0 forks source link

task_07 BFS #217

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 

/baldin_dima/task07_bfs/

Original issue reported on code.google.com by dmitryba...@gmail.com on 23 Apr 2013 at 8:18

GoogleCodeExporter commented 9 years ago 
0. Warnings:
BFS.cpp: In function 'void WriteGraph(std::vector<std::vector<int> >&, 
std::vector<int>&, std::vector<int>&)':
BFS.cpp:58:33: warning: comparison between signed and unsigned integer 
expressions [-Wsign-compare]

1. Решение неверное:
length 0, parent 0
length 2, parent 4
length 3, parent 18
length 1, parent 1
length 0, parent 0
length 6, parent 13
length 4, parent 20
length 3, parent 2
length 0, parent 0
length 0, parent 0
length 4, parent 3
length 0, parent 0
length 5, parent 7
length 0, parent 0
length 2, parent 4
length 0, parent 0
length 3, parent 15
length 2, parent 4
length 0, parent 0
length 3, parent 2

Почему: Например, для 5ой вершины Вы 
указываете расстояние 0, в то время как эта 
вершина вообще недостижима из 1ой (откуда 
запускается BFS).

Решение не принято.

Original comment by aivyu...@gmail.com on 28 Apr 2013 at 7:57

GoogleCodeExporter commented 9 years ago 
И еще. Вы реализовали только на матрице 
смежности. Нужно еще на списках смежности.

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

Original comment by aivyu...@gmail.com on 28 Apr 2013 at 7:59

GoogleCodeExporter commented 9 years ago 
сделал 2 версии, исправил ошибки

Original comment by dmitryba...@gmail.com on 2 May 2013 at 12:54

GoogleCodeExporter commented 9 years ago 
Warnings:
bfs_matrix.cpp: In function ‘void read_graph(std::vector<std::vector<int, 
std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > 
>&, std::vector<clr, std::allocator<clr> >&, std::vector<int, 
std::allocator<int> >&, std::vector<int, std::allocator<int> >&)’:
bfs_matrix.cpp:15: warning: format ‘%d’ expects type ‘int*’, but 
argument 3 has type ‘size_t*’
bfs_matrix.cpp:15: warning: format ‘%d’ expects type ‘int*’, but 
argument 4 has type ‘size_t*’
bfs_matrix.cpp:15: warning: format ‘%d’ expects type ‘int*’, but 
argument 3 has type ‘size_t*’
bfs_matrix.cpp:15: warning: format ‘%d’ expects type ‘int*’, but 
argument 4 has type ‘size_t*’
bfs_matrix.cpp: In function ‘void print_vector(std::vector<std::vector<int, 
std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > 
>&, std::vector<int, std::allocator<int> >&, std::vector<int, 
std::allocator<int> >&)’:
bfs_matrix.cpp:64: warning: format ‘%d’ expects type ‘int’, but 
argument 3 has type ‘long unsigned int’
bfs_matrix.cpp:64: warning: format ‘%d’ expects type ‘int’, but 
argument 3 has type ‘long unsigned int’

1. Приложение падает со следующим 
сообщением:
x(3009) malloc: *** mmap(size=3377596641316864) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
libc++abi.dylib: terminate called throwing an exception
Abort trap: 6

С решением на списках то же самое.

Original comment by aivyu...@gmail.com on 10 May 2013 at 8:35

GoogleCodeExporter commented 9 years ago

Original comment by dmitryba...@gmail.com on 18 May 2013 at 1:24

GoogleCodeExporter commented 9 years ago 
Та же фигня. Причем снова проезд по памяти. 
И, как я уже говорил, эти варнинги не 
случайны.
Я прогнал под отладчиком. У меня падение 
памяти как раз на Ваших scanf.

Заменил size_t на int, а %u на int. Заработало. Я 
закоммитил. Не забудьте сделать svn update.

Решение верное. Решение принято.

Original comment by aivyu...@gmail.com on 19 May 2013 at 11:02