در یک جمع n نفره، فردی را باحال گویند که همه او را بشناسند ولی او هیچکس را نشناسد اگر در این جمع دقیقاً یک فرد باحال داشته باشیم، برنامه ایی برای تشخیص این فرد بنویسید ...
در یک جمع n نفره، فردی را باحال گویند که همه او را بشناسند ولی او هیچکس را نشناسد اگر در این جمع دقیقاً یک فرد باحال داشته باشیم، برنامه ایی برای تشخیص این فرد بنویسید ...
اگر فرد x فرد y را بشناسد، پس x با حال نیست.
اگر فرد x فرد y را نشناسد، پس y با حال نیست.
چون هر دو اصل بر اساس مساله "شناختن" هستند، یک ماتریس (آرایه دو بعدی) می سازیم
که مشخص کند که آیا فلان فرد x (سطر x) فرد y (ستون y) را می شناسد (مقدار 1) یا
نمی شناسد (مقدار 0) :
A[x][y] = 0
یا
A[x][y] = 1
چون هر فردی خودش را می شناسد، می توان فرض کرد که همواره A[x][x] = 1
اگر در این ماتریس فرد باحال ای مثلا z وجود داشته باشد، بایستی :
1) برای هر مقدار x مقدار A[x][z] = 1 باشد، یعنی ستون z ام ماتریس تماما مقدار 1 داشته باشد.
2) برای هر مقدار y بجز y = z مقدار A[z][y] = 0 باشد، یعنی سطر z ام ماتریس بجز در [A[z][z در بقیه
اندیس ها مقدار اش 0 باشد.
ما به ماتریس یا تابعی نیاز خواهیم داشت که مشخص کند که آیا فرد x فرد y را می شناسد یا خیر :
کد:
int know[n][n];
int Know(int x, int y);
هر دو روش نتیجه یکسانی خواهند داشت، به هر حال شناختن افراد جزو معلومات اولیه مساله است
که بایستی به ما داده شود.
تابع زیر می تواند فرد باحال را پیدا کند و شماره اش را برگرداند :
کد:
int Baahaal()
{
int x, y, z;
for (x = 0; x < n; x++)
{
for (y = 0; y < n; y++)
if (know[x][y] == 0)
break;
if (y == n)
{
for (z = 0; z < n; z++)
if ((know[z][x] == 1) && (z != x))
break;
if (z == n)
return x;
}
}
}
مشکلم تا حدی رفع شده اما سوالی که برام ایجاد شده ...
ماتریس اولیه رو چطور ایجاد کنیم ؟؟
کاربر ؟
برنامه نویس ؟
این هم برنامه کامل با آرایه پیش فرض 5 در 5 ::
کد:
#include <stdio.h>
#include <conio.h>
const int n = 5 ;
int search ( int a [n][n] ) ;
void main ()
{
int i , j , p , arr [n][n] = { {1,0,1,1,1} , {0,1,1,1,1} , {0,0,1,0,0} , {1,1,1,1,1} , {1,1,1,1,1} } ;
printf ( "\n\t\t" ) ;
for ( i = 0 ; i < n ; i ++ )
for ( j = 0 ; j < n ; j ++ )
{
printf ( "%d " , arr [i][j] ) ;
if ( j == n - 1 )
printf ( "\n\t\t" ) ;
}
printf ( "**************************************************" ) ;
p = search ( arr ) ;
printf ( "\n\n\t\t Moqeeyate farde Bahal :: %d" , p ) ;
getch () ;
}
int search ( int a [n][n] )
{
int x , y , z , position , count_1 , count_2 ;
for ( x = 0 ; x < n ; x ++ )
{
count_1 = 0 ;
count_2 = 0 ;
for ( y = 0 ; y < n ; y ++ )
if ( a [x][y] == 0 )
count_1 ++ ;
if ( count_1 == n - 1 )
{
for ( z = 0 ; z < n ; z ++ )
if ( a [z][x] == 1 )
count_2 ++ ;
if ( count_2 == n )
position = x ;
}
}
return position ;
}
اصولا برنامه نویس از قبل اطلاعات شناسایی افراد رو نمی دونه، پس از کاربر باید پرسیده شود.
مثلا بپرسد که آیا فرد شماره 0 فرد شماره 4 را می شناسد یا خیر و بر اساس پاسخ کاربر،
مقدار [a[0][4 را تعیین کند.
