الگوریتم کولهپشتی، یک الگوریتم از نوع حریصانه هست. در این مطلب در مورد الگوریتم کولهپشتی یک و صفر (0/1 knapsack algorithm) مینویسم. برای مثال فرض کنید یک کوله پشتی با حجم ۹۰ لیتر دارید؛ و وسایلی که دارید علاوه بر حجم برای شما یک ارزش یا اهمیت دارند و احتمالا همه آنها جا نمیشوند. حال به چه صورت وسایل را انتخاب میکنید تا بیشترین ارزش را در کوله پشتی خود داشته باشید؟ در الگوریتم کولهپشتی یک و صفر یا یک شی انتخاب میشود و یا خیر! امکان برش و تکه کردن نیست.
سلام! به مسئلهای برخوردم که نیاز داشت یه آرایه با طول نامعلوم رو از کاربر بگیریم. اینطوری که کاربر شروع میکنه به وارد کردن ورودیها تا زمانی که کلمه end رو بزنه و تموم کنه. مسئله سادهای هست و در کل زیاد چیز شاخی نیست!!
چالشش اینه که ما تعداد اعضا رو نمیدونیم و طول آرایه هم ثابته کنه، پس در حالت عادی مجبوریم ورودیها رو بریزیم تو یه لیست تا آخرش که کار کاربر تموم شد همه رو مثلا منتقل کنیم به یه آرایه با طول لیسته، یعنی داریم دو بار هر عضو رو بررسی میکنیم که هزینه زمانی اینجا میشه 2n(معادل O(n)) از طرفی توی زبانی مثل C که اصلا لیست نیست و باید مثلا از SLL(به انگلیسی: Singly Linked List و به فارسی: فهرست پیوندی یکطرفه) استفاده کرد.
#include <stdio.h>
#include <stdlib.h>
double* rec(int i) {
char input[100]; // Adjust the input string size as needed
fgets(input, sizeof(input), stdin);
if (strcmp(input, "end\n") == 0) {
double* result = (double*)malloc(i * sizeof(double));
return result;
}
double* arr = rec(i + 1);
sscanf(input, "%lf", &arr[i]);
return arr;
}
int main() {
double* result = rec(0);
// Printing the result
for (int i = 0; result[i] != 0.0; ++i) {
printf("%lf ", result[i]);
}
free(result); // Free the allocated memory
return 0;
}
مشابه این کد در پایتون به این شکل نوشته میشود(برای آرایه از numpy استفاده شده).
from numpy import np
def rec(i=0):
inp = input()
if inp == "end":
return np.zeros(i)
arr = rec(i + 1)
arr[i] = int(inp)
return arr
در واقع این شیوه به شکلی هوشمندانه از پشته(به انگلیسی: stack) خود سیستم برای ذخیره موقتی اعضا و شمارش آن ها استفاده میکنه. اما باید دقت کنید که این روش نامحدود هم نیست چون به اندازه پشته محدود میشه.
روبوکد یک بازی برنامهنویسی است که در آن با زبان جاوا، اقدام به برنامهنویسی کردن روباتهای کوچکی میکنید که با بقیهٔ روباتها باید بجنگند. مبارزه میتواند به صورت تکبهتک با یک روبات دیگر یا به صورت گروهی با مثلاً ۹ روبات دیگر باشد. هرچند که باید روباتهای خود را به زبان جاوا بنویسید، اما دانش عمیقی از این زبان مورد نیاز نیست و در صورتی برنامهنویس یکی از زبانها از همین خانواده باشید، میتوانید بهراحتی یک روبات بسازید.
اینکه برای یادگیری برنامهنویسی دانستن زبان انگلیسی لازم هست یا نه، پرسش بسیاری از کسانی هست که میخواهند برنامهنویسی را شروع به یادگیری کنند. در این پست بنده با توجه به تجربهی خودم سعی میکنم به این پرسش جواب دهم. اگر نمیخواهید کل مطلب را بخوانید، جواب کوتاه این پرسش در یک جمله این است که «بله، برای یادگیری برنامهنویسی باید حتما انگلیسی هم یاد بگیرید»