طراحي الگوريتم
چهارده سال پیش منتشر شده
تعداد بازدید: 5127
کد پروژه: 2156
شرح پروژه
1) با استفاده از روش تقسيم و حل الگو ريتم کارآمدي با زمان اجراي كمتر از خطي بنويسيد که در يک جدول(آرايه) n*n يک مقدار مفروض را جستجو کند. اين جدول در راستاي سطرها و ستون ها مرتب شده اند.
ورودي فايل in.txt است كه در سطر اول آن عدد n مشخص شده و درn سطر بعدي فايل : در هر سطر n عدد مربوط به آن سطر آمده است.
مثال:
5
1 4 7 12 20
2 6 15 17 33
5 8 19 21 34
9 10 22 23 35
2) يك الگوريتم كارا براي پيدا كردن بزرگترين زير رشته¬اي كه هم به صورت پيشرو و هم به صورت عقبرو در رشته ورودي مشاهده مي¬شود، ارائه دهيد. دو زير رشته پيشرو و عقبرو نبايد با هم اشتراك داشته باشد. الگوريتم شما بايد در زمان O(n2) انجام شود. در زير چند مثال آمده است:
• For T = ALGORITHM, your algorithm should return 0.
• For T = CPEGCOMP, your algorithm should return 1, for the substring C or P.
• For T = MANYDYNAMICPROGRAMMING, your algorithm should return 4,
for the substring MANY. Note that neither MANYD or MANYDYNAM count,
since each overlaps its backwards occurrence in T.
3) Suppose we are given an array A[1..n] of distinct numbers with the special property that A[1] > A[2] and A[n − 1] < A[n]. We say that an element A[x] is a local minimum if it is less than both its neighbors, or more formally, if A[x − 1] > A[x] and A[x] < A[x + 1]. For example, there are two local minima (3 and 1) in the following array: 9 3 7 2 1 4 5
We can obviously find a local minimum in O(n) time by scanning through the array. Describe and analyze an algorithm that finds a local minimum in O(log n) time. If there is more than one local minimum, finding any of them is fine. [Hint: With the given boundary conditions, the array must have at least one local minimum. ]
قابل تحویل:
مهارت ها و تخصص های مورد نیاز
بودجه
5,000 تومان تا 100,000 تومان
مهلت برای انجام
30روز
وضعیت مناقصه
انجام شده
درباره کارفرما
عضویت شانزده سال پیش
