المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱:سوال ۲

سوال ۲

فرض کنید $A$ و $B$ ماتریس‌های $N\times N$ هستند که در هر درایه‌ی آن‌ها یک عدد صحیح قرار داده شده است.

الف) مجموعه‌ی $S=\{1,2,…,N\}$ مفروض است. الگوریتمی بنویسید که یک ماتریس $N\times N$، $D$ را در نظر بگیرد و برای هر درایه‌ی ماتریس $A$ در صورتی که آن درایه متعلق به مجموعه‌ی $S$ باشد درایه‌ی متناظر را در ماتریس $D$ مساوی یک و در غیر این صورت مساوی صفر قرار دهد.

ب) الگوریتمی بنویسید که دو بردار $N$ تایی $IQ$ و $JQ$ را در نظر بگیرد و در صورتی که در سطر $i$ ام ماتریس $A$ عضو تکراری وجود داشته باشد مولفه‌ی $i$ ام بردار $IQ$ را مساوی یک و در غیر این صورت مساوی صفر قرار دهد. مشابها چنانچه در ستون $j$ ام ماتریس $A$ عضو تکراری وجود داشته باشد مولفه‌ی $j$ ام بردار $JQ$ را مساوی یک و در غیر این صورت مساوی صفر قرار دهد.

ج) الگوریتمی بنویسید که حاصل ضرب قطری $A\times B$ را به دست آورده& در یک ماتریس $N\times N$ دیگر، $C$، قرار دهد. ضرب قطری دو ماتریس، $A\times B$، شبیه ضرب معمولی آن دو می‌باشد. با این تفاوت که به جای ضرب شدن سطر $i$ ام ماتریس اول در ستون $j$ ام ماتریس دوم، قطر اصلی $i$ ام ماتریس اول در قطر فرعی $j$ ام ماتریس دوم ضرب می‌شود. برای مثال قطرهای اصلی و فرعی یک ماتریس $5\times 5$ در شکل زیر نشان داده شده است:

د) با استفاده از الگوریتم‌های فوق، الگوریتمی بنویسید که در صورتی که اعضای دو ماتریس $A$ و $B$ متعلق به مجموعه‌ی $S$ باشند و در هیچ سطر و ستون آن‌ها عدد تکراری وجود نداشته باشد، حاصل ضرب قطری $A\times B$ را محاسبه نمایید.


ابزار صفحه