C/C++

R

Reve0ke

Гостин
ivan1real напиша:
Да се најдат сите природни броеви помали од дадениот природен број n внесен преку тастатура, кои се палиндроми.

Палиндром е број кој се чита исто и одназад нанапред, како и однапред наназад.

Со for циклус иде ова ?
Кликни за повеќе...
Ами како ке стасаш до n.
 
back_rest

back_rest

ex mod coder
Член од
19 јули 2006
Мислења
1.590
Поени од реакции
107
ivan1real напиша:
Да се најдат сите природни броеви помали од дадениот природен број n внесен преку тастатура, кои се палиндроми.

Палиндром е број кој се чита исто и одназад нанапред, како и однапред наназад.

Со for циклус иде ова ?
Кликни за повеќе...
Иде со циклус. Прави си го каков ти одговара, било for, while, do, goto или можда и рекурзија. Твоја желба.
 
bowl

bowl

.
Член од
30 јануари 2007
Мислења
8.344
Поени од реакции
1.307
Го напраив програмчето, сега ми треба помош со одредување на времето на извршување на програмот, и неговата комплексност.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int i,n,cifra,broj,kopija,obraten;

printf("Vnesi broj:\n");
scanf("%d",&n);
for (i=n;i>=0;i--){
obraten=0;
kopija=i;

while(kopija>0){
cifra=kopija%10;
obraten=10*obraten+cifra;
kopija=kopija/10;
}
if(i==obraten)
printf("%d\n",i);
}


system("PAUSE");
return 0;
}
Кликни за повеќе...
 
SkyDriver

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
ivan1real напиша:
Го напраив програмчето, сега ми треба помош со одредување на времето на извршување на програмот, и неговата комплексност.
Кликни за повеќе...
Незнам дали воопшто може да му се одреди run-time на некој алгоритам затоа што тој се извршува на Ram такада на различен компјутер ќе имаш различно run-time време. Иначе еве ти код кој ти кажува приближно точно време (имај во предвид дека „празен“ loop до 100000000 ќе помине за поамлце од пола секунда).
 
bowl

bowl

.
Член од
30 јануари 2007
Мислења
8.344
Поени од реакции
1.307
SkyDriver напиша:
Незнам дали воопшто може да му се одреди run-time на некој алгоритам затоа што тој се извршува на Ram такада на различен компјутер ќе имаш различно run-time време. Иначе еве ти код кој ти кажува приближно точно време (имај во предвид дека „празен“ loop до 100000000 ќе помине за поамлце од пола секунда).
Кликни за повеќе...
Не сум сигурен дека е тоа е тоа што ми треба. Еве што пишува

4. Комплексност

Се проценува времето на извршување на предложениот програм, и се дава проценка на редот на комплексноста на програмот.
Кликни за повеќе...
Знам имаше една формула, но тоа беше кај низите, дали е истото незнам :)

Фала во секој случај ;)
 
back_rest

back_rest

ex mod coder
Член од
19 јули 2006
Мислења
1.590
Поени од реакции
107
Комплексност и време на извршување се различни ствари.

Во твојот код, комплексноста грубо проценета е O(n*log10(n) / 2) каде што n ти е внесениот број. Log10 пошто внатрешниот циклус се извршува толку колку што цифри има бројот, а делено со два за некое грубо усреднување.

Времето на извршување е различно на различни компјутери/платформи.
 
Petkovsky

Petkovsky

Член од
14 јануари 2008
Мислења
1.341
Поени од реакции
162
HsIlOmEdUs напиша:
Комплексност и време на извршување се различни ствари.

Во твојот код, комплексноста грубо проценета е O(n*log10(n) / 2) каде што n ти е внесениот број. Log10 пошто внатрешниот циклус се извршува толку колку што цифри има бројот, а делено со два за некое грубо усреднување.

Времето на извршување е различно на различни компјутери/платформи.
Кликни за повеќе...
Без двојката само, зашто не се гледаат коефициенти кај О нотација.
 
*LIDIJA*

*LIDIJA*

Член од
4 декември 2008
Мислења
28
Поени од реакции
13
Јас имам пак проблем со задачва :toe:
Следнава програмава е да определи дали внесен збор е палиндром и ок е, али треба да бара и во дадениот збор дали има и подзбор кој е исто така палиндром. Ве молам помогнетеми многу ми е итно а незнам како да го направам тоа да бара подзбор палиндром.
Ви благодарам однапред.

#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

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
*LIDIJA* напиша:
Јас имам пак проблем со задачва :toe:
Следнава програмава е да определи дали внесен збор е палиндром и ок е, али треба да бара и во дадениот збор дали има и подзбор кој е исто така палиндром. Ве молам помогнетеми многу ми е итно а незнам како да го направам тоа да бара подзбор палиндром.
Ви благодарам однапред.
Кликни за повеќе...
Хмм... решение што ми текнува од „прва рака“ вака би му дошло... првин споредуваш по 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++; }
Ете ти објаснување, на тебе останува само да го претвориш во код.
Пробај, па ако неможеш да се снајдеш ќе пишеме и код. :)
 
*LIDIJA*

*LIDIJA*

Член од
4 декември 2008
Мислења
28
Поени од реакции
13
Хмммм....немам идеја како да го напишам ова во код :nesum:
Ај те молам ако знаеш кажи ми,пукнав со оваа задача.
 
SkyDriver

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
*LIDIJA* напиша:
Хмммм....немам идеја како да го напишам ова во код :nesum:
Ај те молам ако знаеш кажи ми,пукнав со оваа задача.
Кликни за повеќе...
Изволте: :)

Код: 
#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@skydriver-desktop:~/Desktop$ gcc palindrome.c -o test.c
skydriver@skydriver-desktop:~/Desktop$ ./test.c

Please enter input string: kajgana

Current string = ka, reversed string = ak.
ka != ak, hence ka is not a palindrome.

Current string = aj, reversed string = ja.
aj != ja, hence aj is not a palindrome.

Current string = jg, reversed string = gj.
jg != gj, hence jg is not a palindrome.

Current string = ga, reversed string = ag.
ga != ag, hence ga is not a palindrome.

Current string = an, reversed string = na.
an != na, hence an is not a palindrome.

Current string = na, reversed string = an.
na != an, hence na is not a palindrome.

Current string = kaj, reversed string = jak.
kaj != jak, hence kaj is not a palindrome.

Current string = ajg, reversed string = gja.
ajg != gja, hence ajg is not a palindrome.

Current string = jga, reversed string = agj.
jga != agj, hence jga is not a palindrome.

Current string = gan, reversed string = nag.
gan != nag, hence gan is not a palindrome.

Current string = ana, reversed string = ana.
ana = ana, hence ana is a palindrome.

Current string = kajg, reversed string = gjak.
kajg != gjak, hence kajg is not a palindrome.

Current string = ajga, reversed string = agja.
ajga != agja, hence ajga is not a palindrome.

Current string = jgan, reversed string = nagj.
jgan != nagj, hence jgan is not a palindrome.

Current string = gana, reversed string = anag.
gana != anag, hence gana is not a palindrome.

Current string = kajga, reversed string = agjak.
kajga != agjak, hence kajga is not a palindrome.

Current string = ajgan, reversed string = nagja.
ajgan != nagja, hence ajgan is not a palindrome.

Current string = jgana, reversed string = anagj.
jgana != anagj, hence jgana is not a palindrome.

Current string = kajgan, reversed string = nagjak.
kajgan != nagjak, hence kajgan is not a palindrome.

Current string = ajgana, reversed string = anagja.
ajgana != anagja, hence ajgana is not a palindrome.

Current string = kajgana, reversed string = anagjak.
kajgana != anagjak, hence kajgana is not a palindrome.
Кликни за повеќе...
 
*LIDIJA*

*LIDIJA*

Член од
4 декември 2008
Мислења
28
Поени од реакции
13
Фала многу стварно многу ми помогна:je:
ФАЛАААААА!!!!!!!!!!!!

А може да ми кажиш како се одредува комплексност?
 
SkyDriver

SkyDriver

Would like my bananna ?
Член од
31 јули 2008
Мислења
2.140
Поени од реакции
221
*LIDIJA* напиша:
Фала многу стварно многу ми помогна:je:
ФАЛАААААА!!!!!!!!!!!!
Кликни за повеќе...
Но проблемос :)

*LIDIJA* напиша:
А може да ми кажиш како се одредува комплексност?
Кликни за повеќе...
Математички точнo незнам како ќе му дојде, ама од прилика вака некако мислам дека би му дошло:

O(n+(n*(m*log10(x)))

n = должината на стрингот
m = комбинациите
x = број на карактерите по комбинација

Е сега, не сум баш сигурен колку приближно е точна горната формула (можда ги замешав работите :S), али ако е точна горната формула за поточни резултати ќе треба да ги додадеш и останатите операции. :toe:
 
You must log in or register to reply here.

Kajgana Shop

На врв Bottom