R
Reve0ke
Гостин
Ами како ке стасаш до n.
C/C++
- Креатор на темата Драган
- Време на започнување
back_rest
ex mod coder
- Член од
- 19 јули 2006
- Мислења
- 1.590
- Поени од реакции
- 107
Иде со циклус. Прави си го каков ти одговара, било for, while, do, goto или можда и рекурзија. Твоја желба.
SkyDriver
Would like my bananna ?
Незнам дали воопшто може да му се одреди run-time на некој алгоритам затоа што тој се извршува на Ram такада на различен компјутер ќе имаш различно run-time време. Иначе еве ти код кој ти кажува приближно точно време (имај во предвид дека „празен“ loop до 100000000 ќе помине за поамлце од пола секунда).
bowl
.
- Член од
- 30 јануари 2007
- Мислења
- 8.344
- Поени од реакции
- 1.307
Не сум сигурен дека е тоа е тоа што ми треба. Еве што пишува
Знам имаше една формула, но тоа беше кај низите, дали е истото незнам
Фала во секој случај
back_rest
ex mod coder
- Член од
- 19 јули 2006
- Мислења
- 1.590
- Поени од реакции
- 107
Комплексност и време на извршување се различни ствари.
Во твојот код, комплексноста грубо проценета е O(n*log10
/ 2) каде што n ти е внесениот број. Log10 пошто внатрешниот циклус се извршува толку колку што цифри има бројот, а делено со два за некое грубо усреднување.
Времето на извршување е различно на различни компјутери/платформи.
Во твојот код, комплексноста грубо проценета е O(n*log10
/ 2) каде што n ти е внесениот број. Log10 пошто внатрешниот циклус се извршува толку колку што цифри има бројот, а делено со два за некое грубо усреднување.Времето на извршување е различно на различни компјутери/платформи.
- Член од
- 14 јануари 2008
- Мислења
- 1.341
- Поени од реакции
- 162
Комплексност и време на извршување се различни ствари.
Во твојот код, комплексноста грубо проценета е O(n*log10
Времето на извршување е различно на различни компјутери/платформи.
Без двојката само, зашто не се гледаат коефициенти кај О нотација.
back_rest
ex mod coder
- Член од
- 19 јули 2006
- Мислења
- 1.590
- Поени од реакции
- 107
I stand corrected.
- Член од
- 4 декември 2008
- Мислења
- 31
- Поени од реакции
- 19
Јас имам пак проблем со задачва 
Следнава програмава е да определи дали внесен збор е палиндром и ок е, али треба да бара и во дадениот збор дали има и подзбор кој е исто така палиндром. Ве молам помогнетеми многу ми е итно а незнам како да го направам тоа да бара подзбор палиндром.
Ви благодарам однапред.
#include <stdio.h>
#include <string.h>
unsigned int get_string_length(const char *string)
{
int i;
int string_length = 0;
for (i = 0; string != 0 && string != '\n'; ++i)
++string_length;
return string_length;
}
void reverse(const char *in_string, char *rev_string)
{
int i, j;
unsigned int length;
length = get_string_length(in_string);
for (i = length-1, j = 0; i >= 0; --i, ++j)
rev_string[j] = in_string;
rev_string[j] = 0;
}
int main()
{
const int max_size = 100;
int string_length = 0;
char string[max_size];
char reverse_string[max_size];
printf("\nPlease enter input string: ");
fgets(string, max_size, stdin);
string_length = get_string_length(string);
string[string_length] = 0;
reverse(string, reverse_string);
if (!strcmp(string, reverse_string)) {
printf("\nEntered string = %s, reversed string = %s."
"\n%s = %s, hence %s is a palindrome.\n",
string, reverse_string, string, reverse_string, string);
} else {
printf("\nEntered string = %s, reversed string = %s."
"\n%s != %s, hence %s is not a palindrome.\n",
string, reverse_string, string, reverse_string, string);
}
system("PAUSE");
return 0;
}
Следнава програмава е да определи дали внесен збор е палиндром и ок е, али треба да бара и во дадениот збор дали има и подзбор кој е исто така палиндром. Ве молам помогнетеми многу ми е итно а незнам како да го направам тоа да бара подзбор палиндром.
Ви благодарам однапред.
#include <stdio.h>
#include <string.h>
unsigned int get_string_length(const char *string)
{
int i;
int string_length = 0;
for (i = 0; string != 0 && string != '\n'; ++i)
++string_length;
return string_length;
}
void reverse(const char *in_string, char *rev_string)
{
int i, j;
unsigned int length;
length = get_string_length(in_string);
for (i = length-1, j = 0; i >= 0; --i, ++j)
rev_string[j] = in_string;
rev_string[j] = 0;
}
int main()
{
const int max_size = 100;
int string_length = 0;
char string[max_size];
char reverse_string[max_size];
printf("\nPlease enter input string: ");
fgets(string, max_size, stdin);
string_length = get_string_length(string);
string[string_length] = 0;
reverse(string, reverse_string);
if (!strcmp(string, reverse_string)) {
printf("\nEntered string = %s, reversed string = %s."
"\n%s = %s, hence %s is a palindrome.\n",
string, reverse_string, string, reverse_string, string);
} else {
printf("\nEntered string = %s, reversed string = %s."
"\n%s != %s, hence %s is not a palindrome.\n",
string, reverse_string, string, reverse_string, string);
}
system("PAUSE");
return 0;
}
SkyDriver
Would like my bananna ?
Јас имам пак проблем со задачва
Следнава програмава е да определи дали внесен збор е палиндром и ок е, али треба да бара и во дадениот збор дали има и подзбор кој е исто така палиндром. Ве молам помогнетеми многу ми е итно а незнам како да го направам тоа да бара подзбор палиндром.
Ви благодарам однапред.
Хмм... решение што ми текнува од „прва рака“ вака би му дошло... првин споредуваш по 2 карактери од стрингот, потоа по 3 карактери, па по 4... и се така до должината на стрингот.
Еве ти и „графички“ пример:
Ако внесениот збор е: kajgana
Тогаш:
Споредба со 2 карактери:
1. kajgana
2. kajgana
3. kajgana
4. kajgana
5. kajgana
6. kajgana
Потоа споредба со 3 карактери:
1. kajgana
2. kajgana
3. kajgana
4. kajgana
5. kajgana
Па потоа со по 4, па со по 5 карактери... и се така до должината на стрингот.
Е сега, кога ќе споредуваш ќе имаш и услов
Код:
if (karakterite==reverse(karakterite) { brNaPalindromi++; }Ете ти објаснување, на тебе останува само да го претвориш во код.
Пробај, па ако неможеш да се снајдеш ќе пишеме и код.
SkyDriver
Would like my bananna ?
Изволте:
Код:
#include <stdio.h>
#include <string.h>
unsigned int get_string_length(const char *string) {
int i;
int string_length = 0;
for (i = 0; string[i] != 0 && string[i] != '\n'; ++i)
++string_length;
return string_length;
}
void substr(const char *in_string, char *substring, int s, int n) {
int i, j=0;
for(i=s; i<n; ++i, ++j)
substring[j] = in_string[i];
substring[j] = 0;
}
void reverse(const char *in_string, char *rev_string) {
int i, j;
unsigned int length;
length = get_string_length(in_string);
for (i = length-1, j = 0; i >= 0; --i, ++j)
rev_string[j] = in_string[i];
rev_string[j] = 0;
}
int main() {
const int max_size = 100;
int string_length = 0;
char string[max_size];
char reverse_string[max_size];
printf("\nPlease enter input string: ");
fgets(string, max_size, stdin);
string_length = get_string_length(string);
string[string_length] = 0;
int i, j, n, no=1;
for(i=0; i<string_length; i++) {
++no;
int tmp = no;
int t;
for(t=0; tmp<=string_length; ++tmp, ++t) {
char substring[max_size];
char reverse_substring[max_size];
substr(string, substring, t, tmp);
reverse(substring, reverse_substring);
if (!strcmp(substring, reverse_substring)) {
printf("\nCurrent string = %s, reversed string = %s."
"\n%s = %s, hence %s is a palindrome.\n",
substring, reverse_substring, substring, reverse_substring, substring);
} else {
printf("\nCurrent string = %s, reversed string = %s."
"\n%s != %s, hence %s is not a palindrome.\n",
substring, reverse_substring, substring, reverse_substring, substring);
}
}
}
return 0;
}Јас го тестирав со „kajgana“, ете ги подоле и резултатите, мислам дека дава точни резултати, ако налеташ на грешка кажи.
SkyDriver
Would like my bananna ?
Но проблемос
Математички точнo незнам како ќе му дојде, ама од прилика вака некако мислам дека би му дошло:
O(n+(n*(m*log10(x)))
n = должината на стрингот
m = комбинациите
x = број на карактерите по комбинација
Е сега, не сум баш сигурен колку приближно е точна горната формула (можда ги замешав работите :S), али ако е точна горната формула за поточни резултати ќе треба да ги додадеш и останатите операции.
